Signed-off-by: Nathan Jones <nathanj@insightbb.com> --- lib/libalpm/Makefile.am | 1 + lib/libalpm/alpm.h | 12 ++ lib/libalpm/alpm_list.c | 18 +++ lib/libalpm/alpm_list.h | 1 + lib/libalpm/be_files.c | 19 +++ lib/libalpm/db.h | 3 +- lib/libalpm/delta.c | 265 ++++++++++++++++++++++++++++++++++++++++++++ lib/libalpm/delta.h | 45 ++++++++ lib/libalpm/package.c | 15 +++ lib/libalpm/package.h | 1 + lib/libalpm/po/POTFILES.in | 1 + 11 files changed, 380 insertions(+), 1 deletions(-) create mode 100644 lib/libalpm/delta.c create mode 100644 lib/libalpm/delta.h diff --git a/lib/libalpm/Makefile.am b/lib/libalpm/Makefile.am index 6948239..49ce14c 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 6eda210..5f37d82 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 5671b4a..2301411 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 a2a06f4..8fce280 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 2bfdb95..59155cf 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 3ee4977..16e1298 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 0000000..00ed46c --- /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 0000000..67dbeb4 --- /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 38e6e4c..6a8e0d8 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; @@ -725,6 +739,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 42ebe0e..daaeb36 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 caf68c3..97df339 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 -- 1.5.3.4