libalpm
Arch Linux Package Manager Library
|
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: */