libalpm
Arch Linux Package Manager Library
delta.c
Go to the documentation of this file.
00001 /*
00002  *  delta.c
00003  *
00004  *  Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org>
00005  *  Copyright (c) 2007-2006 by Judd Vinet <jvinet@zeroflux.org>
00006  *
00007  *  This program is free software; you can redistribute it and/or modify
00008  *  it under the terms of the GNU General Public License as published by
00009  *  the Free Software Foundation; either version 2 of the License, or
00010  *  (at your option) any later version.
00011  *
00012  *  This program is distributed in the hope that it will be useful,
00013  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  *  GNU General Public License for more details.
00016  *
00017  *  You should have received a copy of the GNU General Public License
00018  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
00019  */
00020 
00021 #include <stdlib.h>
00022 #include <string.h>
00023 #include <stdint.h> /* intmax_t */
00024 #include <limits.h>
00025 #include <sys/types.h>
00026 #include <regex.h>
00027 
00028 /* libalpm */
00029 #include "delta.h"
00030 #include "alpm_list.h"
00031 #include "util.h"
00032 #include "log.h"
00033 #include "graph.h"
00034 
00035 static alpm_list_t *graph_init(alpm_list_t *deltas, int reverse)
00036 {
00037     alpm_list_t *i, *j;
00038     alpm_list_t *vertices = NULL;
00039     /* create the vertices */
00040     for(i = deltas; i; i = i->next) {
00041         alpm_graph_t *v = _alpm_graph_new();
00042         if(!v) {
00043             alpm_list_free(vertices);
00044             return NULL;
00045         }
00046         alpm_delta_t *vdelta = i->data;
00047         vdelta->download_size = vdelta->delta_size;
00048         v->weight = LONG_MAX;
00049         v->data = vdelta;
00050         vertices = alpm_list_add(vertices, v);
00051     }
00052 
00053     /* compute the edges */
00054     for(i = vertices; i; i = i->next) {
00055         alpm_graph_t *v_i = i->data;
00056         alpm_delta_t *d_i = v_i->data;
00057         /* loop a second time so we make all possible comparisons */
00058         for(j = vertices; j; j = j->next) {
00059             alpm_graph_t *v_j = j->data;
00060             alpm_delta_t *d_j = v_j->data;
00061             /* We want to create a delta tree like the following:
00062              *          1_to_2
00063              *            |
00064              * 1_to_3   2_to_3
00065              *   \        /
00066              *     3_to_4
00067              * If J 'from' is equal to I 'to', then J is a child of I.
00068              * */
00069             if((!reverse && strcmp(d_j->from, d_i->to) == 0) ||
00070                     (reverse && strcmp(d_j->to, d_i->from) == 0)) {
00071                 v_i->children = alpm_list_add(v_i->children, v_j);
00072             }
00073         }
00074         v_i->childptr = v_i->children;
00075     }
00076     return vertices;
00077 }
00078 
00079 static void graph_init_size(alpm_handle_t *handle, alpm_list_t *vertices)
00080 {
00081     alpm_list_t *i;
00082 
00083     for(i = vertices; i; i = i->next) {
00084         char *fpath, *md5sum;
00085         alpm_graph_t *v = i->data;
00086         alpm_delta_t *vdelta = v->data;
00087 
00088         /* determine whether the delta file already exists */
00089         fpath = _alpm_filecache_find(handle, vdelta->delta);
00090         if(fpath) {
00091             md5sum = alpm_compute_md5sum(fpath);
00092             if(md5sum && strcmp(md5sum, vdelta->delta_md5) == 0) {
00093                 vdelta->download_size = 0;
00094             }
00095             FREE(md5sum);
00096             FREE(fpath);
00097         } else {
00098             char *fnamepart;
00099             CALLOC(fnamepart, strlen(vdelta->delta) + 6, sizeof(char), return);
00100             sprintf(fnamepart, "%s.part", vdelta->delta);
00101             fpath = _alpm_filecache_find(handle, fnamepart);
00102             if(fpath) {
00103                 struct stat st;
00104                 if(stat(fpath, &st) == 0) {
00105                     vdelta->download_size = vdelta->delta_size - st.st_size;
00106                     vdelta->download_size = vdelta->download_size < 0 ? 0 : vdelta->download_size;
00107                 }
00108                 FREE(fpath);
00109             }
00110             FREE(fnamepart);
00111         }
00112 
00113         /* determine whether a base 'from' file exists */
00114         fpath = _alpm_filecache_find(handle, vdelta->from);
00115         if(fpath) {
00116             v->weight = vdelta->download_size;
00117         }
00118         FREE(fpath);
00119     }
00120 }
00121 
00122 
00123 static void dijkstra(alpm_list_t *vertices)
00124 {
00125     alpm_list_t *i;
00126     alpm_graph_t *v;
00127     while(1) {
00128         v = NULL;
00129         /* find the smallest vertice not visited yet */
00130         for(i = vertices; i; i = i->next) {
00131             alpm_graph_t *v_i = i->data;
00132 
00133             if(v_i->state == -1) {
00134                 continue;
00135             }
00136 
00137             if(v == NULL || v_i->weight < v->weight) {
00138                 v = v_i;
00139             }
00140         }
00141         if(v == NULL || v->weight == LONG_MAX) {
00142             break;
00143         }
00144 
00145         v->state = -1;
00146 
00147         v->childptr = v->children;
00148         while(v->childptr) {
00149             alpm_graph_t *v_c = v->childptr->data;
00150             alpm_delta_t *d_c = v_c->data;
00151             if(v_c->weight > v->weight + d_c->download_size) {
00152                 v_c->weight = v->weight + d_c->download_size;
00153                 v_c->parent = v;
00154             }
00155 
00156             v->childptr = (v->childptr)->next;
00157 
00158         }
00159     }
00160 }
00161 
00162 static off_t shortest_path(alpm_list_t *vertices, const char *to, alpm_list_t **path)
00163 {
00164     alpm_list_t *i;
00165     alpm_graph_t *v = NULL;
00166     off_t bestsize = 0;
00167     alpm_list_t *rpath = NULL;
00168 
00169     for(i = vertices; i; i = i->next) {
00170         alpm_graph_t *v_i = i->data;
00171         alpm_delta_t *d_i = v_i->data;
00172 
00173         if(strcmp(d_i->to, to) == 0) {
00174             if(v == NULL || v_i->weight < v->weight) {
00175                 v = v_i;
00176                 bestsize = v->weight;
00177             }
00178         }
00179     }
00180 
00181     while(v != NULL) {
00182         alpm_delta_t *vdelta = v->data;
00183         rpath = alpm_list_add(rpath, vdelta);
00184         v = v->parent;
00185     }
00186     *path = alpm_list_reverse(rpath);
00187     alpm_list_free(rpath);
00188 
00189     return bestsize;
00190 }
00191 
00192 /** Calculates the shortest path from one version to another.
00193  * The shortest path is defined as the path with the smallest combined
00194  * size, not the length of the path.
00195  * @param handle the context handle
00196  * @param deltas the list of alpm_delta_t * objects that a file has
00197  * @param to the file to start the search at
00198  * @param path the pointer to a list location where alpm_delta_t * objects that
00199  * have the smallest size are placed. NULL is set if there is no path
00200  * possible with the files available.
00201  * @return the size of the path stored, or LONG_MAX if path is unfindable
00202  */
00203 off_t _alpm_shortest_delta_path(alpm_handle_t *handle, alpm_list_t *deltas,
00204         const char *to, alpm_list_t **path)
00205 {
00206     alpm_list_t *bestpath = NULL;
00207     alpm_list_t *vertices;
00208     off_t bestsize = LONG_MAX;
00209 
00210     if(deltas == NULL) {
00211         *path = NULL;
00212         return bestsize;
00213     }
00214 
00215     _alpm_log(handle, ALPM_LOG_DEBUG, "started delta shortest-path search for '%s'\n", to);
00216 
00217     vertices = graph_init(deltas, 0);
00218     graph_init_size(handle, vertices);
00219     dijkstra(vertices);
00220     bestsize = shortest_path(vertices, to, &bestpath);
00221 
00222     _alpm_log(handle, ALPM_LOG_DEBUG, "delta shortest-path search complete : '%jd'\n", (intmax_t)bestsize);
00223 
00224     alpm_list_free_inner(vertices, _alpm_graph_free);
00225     alpm_list_free(vertices);
00226 
00227     *path = bestpath;
00228     return bestsize;
00229 }
00230 
00231 static alpm_list_t *find_unused(alpm_list_t *deltas, const char *to, off_t quota)
00232 {
00233     alpm_list_t *unused = NULL;
00234     alpm_list_t *vertices;
00235     alpm_list_t *i;
00236     vertices = graph_init(deltas, 1);
00237 
00238     for(i = vertices; i; i = i->next) {
00239         alpm_graph_t *v = i->data;
00240         alpm_delta_t *vdelta = v->data;
00241         if(strcmp(vdelta->to, to) == 0)
00242         {
00243             v->weight = vdelta->download_size;
00244         }
00245     }
00246     dijkstra(vertices);
00247     for(i = vertices; i; i = i->next) {
00248         alpm_graph_t *v = i->data;
00249         alpm_delta_t *vdelta = v->data;
00250         if(v->weight > quota) {
00251             unused = alpm_list_add(unused, vdelta->delta);
00252         }
00253     }
00254     alpm_list_free_inner(vertices, _alpm_graph_free);
00255     alpm_list_free(vertices);
00256     return unused;
00257 }
00258 
00259 /** \addtogroup alpm_deltas Delta Functions
00260  * @brief Functions to manipulate libalpm deltas
00261  * @{
00262  */
00263 
00264 alpm_list_t SYMEXPORT *alpm_pkg_unused_deltas(alpm_pkg_t *pkg)
00265 {
00266     ASSERT(pkg != NULL, return NULL);
00267     return find_unused(pkg->deltas, pkg->filename, pkg->size * MAX_DELTA_RATIO);
00268 }
00269 
00270 /** @} */
00271 
00272 /** Parses the string representation of a alpm_delta_t object.
00273  * This function assumes that the string is in the correct format.
00274  * This format is as follows:
00275  * $deltafile $deltamd5 $deltasize $oldfile $newfile
00276  * @param handle the context handle
00277  * @param line the string to parse
00278  * @return A pointer to the new alpm_delta_t object
00279  */
00280 alpm_delta_t *_alpm_delta_parse(alpm_handle_t *handle, const char *line)
00281 {
00282     alpm_delta_t *delta;
00283     const int num_matches = 6;
00284     size_t len;
00285     regmatch_t pmatch[num_matches];
00286     char filesize[32];
00287 
00288     /* this is so we only have to compile the pattern once */
00289     if(!handle->delta_regex_compiled) {
00290         /* $deltafile $deltamd5 $deltasize $oldfile $newfile*/
00291         regcomp(&handle->delta_regex,
00292                 "^([^[:space:]]+) ([[:xdigit:]]{32}) ([[:digit:]]+)"
00293                 " ([^[:space:]]+) ([^[:space:]]+)$",
00294                 REG_EXTENDED | REG_NEWLINE);
00295         handle->delta_regex_compiled = 1;
00296     }
00297 
00298     if(regexec(&handle->delta_regex, line, num_matches, pmatch, 0) != 0) {
00299         /* delta line is invalid, return NULL */
00300         return NULL;
00301     }
00302 
00303     CALLOC(delta, 1, sizeof(alpm_delta_t), return NULL);
00304 
00305     /* start at index 1 -- match 0 is the entire match */
00306     len = pmatch[1].rm_eo - pmatch[1].rm_so;
00307     STRNDUP(delta->delta, &line[pmatch[1].rm_so], len, return NULL);
00308 
00309     len = pmatch[2].rm_eo - pmatch[2].rm_so;
00310     STRNDUP(delta->delta_md5, &line[pmatch[2].rm_so], len, return NULL);
00311 
00312     len = pmatch[3].rm_eo - pmatch[3].rm_so;
00313     if(len < sizeof(filesize)) {
00314         strncpy(filesize, &line[pmatch[3].rm_so], len);
00315         filesize[len] = '\0';
00316         delta->delta_size = _alpm_strtoofft(filesize);
00317     }
00318 
00319     len = pmatch[4].rm_eo - pmatch[4].rm_so;
00320     STRNDUP(delta->from, &line[pmatch[4].rm_so], len, return NULL);
00321 
00322     len = pmatch[5].rm_eo - pmatch[5].rm_so;
00323     STRNDUP(delta->to, &line[pmatch[5].rm_so], len, return NULL);
00324 
00325     return delta;
00326 }
00327 
00328 void _alpm_delta_free(alpm_delta_t *delta)
00329 {
00330     FREE(delta->delta);
00331     FREE(delta->delta_md5);
00332     FREE(delta->from);
00333     FREE(delta->to);
00334     FREE(delta);
00335 }
00336 
00337 alpm_delta_t *_alpm_delta_dup(const alpm_delta_t *delta)
00338 {
00339     alpm_delta_t *newdelta;
00340     CALLOC(newdelta, 1, sizeof(alpm_delta_t), return NULL);
00341     STRDUP(newdelta->delta, delta->delta, return NULL);
00342     STRDUP(newdelta->delta_md5, delta->delta_md5, return NULL);
00343     STRDUP(newdelta->from, delta->from, return NULL);
00344     STRDUP(newdelta->to, delta->to, return NULL);
00345     newdelta->delta_size = delta->delta_size;
00346     newdelta->download_size = delta->download_size;
00347 
00348     return newdelta;
00349 }
00350 
00351 /* vim: set ts=2 sw=2 noet: */