/* * 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: */