4 * Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org>
5 * Copyright (c) 2007-2006 by Judd Vinet <jvinet@zeroflux.org>
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program. If not, see <http://www.gnu.org/licenses/>.
25 #include <stdint.h> /* intmax_t */
27 #include <sys/types.h>
32 #include "alpm_list.h"
37 static alpm_list_t
*graph_init(alpm_list_t
*deltas
, int reverse
)
40 alpm_list_t
*vertices
= NULL
;
41 /* create the vertices */
42 for(i
= deltas
; i
; i
= i
->next
) {
43 alpm_graph_t
*v
= _alpm_graph_new();
45 alpm_list_free(vertices
);
48 alpm_delta_t
*vdelta
= i
->data
;
49 vdelta
->download_size
= vdelta
->delta_size
;
52 vertices
= alpm_list_add(vertices
, v
);
55 /* compute the edges */
56 for(i
= vertices
; i
; i
= i
->next
) {
57 alpm_graph_t
*v_i
= i
->data
;
58 alpm_delta_t
*d_i
= v_i
->data
;
59 /* loop a second time so we make all possible comparisons */
60 for(j
= vertices
; j
; j
= j
->next
) {
61 alpm_graph_t
*v_j
= j
->data
;
62 alpm_delta_t
*d_j
= v_j
->data
;
63 /* We want to create a delta tree like the following:
69 * If J 'from' is equal to I 'to', then J is a child of I.
71 if((!reverse
&& strcmp(d_j
->from
, d_i
->to
) == 0) ||
72 (reverse
&& strcmp(d_j
->to
, d_i
->from
) == 0)) {
73 v_i
->children
= alpm_list_add(v_i
->children
, v_j
);
76 v_i
->childptr
= v_i
->children
;
81 static void graph_init_size(alpm_handle_t
*handle
, alpm_list_t
*vertices
)
85 for(i
= vertices
; i
; i
= i
->next
) {
87 alpm_graph_t
*v
= i
->data
;
88 alpm_delta_t
*vdelta
= v
->data
;
90 /* determine whether the delta file already exists */
91 fpath
= _alpm_filecache_find(handle
, vdelta
->delta
);
92 md5sum
= alpm_compute_md5sum(fpath
);
93 if(fpath
&& md5sum
&& strcmp(md5sum
, vdelta
->delta_md5
) == 0) {
94 vdelta
->download_size
= 0;
99 /* determine whether a base 'from' file exists */
100 fpath
= _alpm_filecache_find(handle
, vdelta
->from
);
102 v
->weight
= vdelta
->download_size
;
109 static void dijkstra(alpm_list_t
*vertices
)
115 /* find the smallest vertice not visited yet */
116 for(i
= vertices
; i
; i
= i
->next
) {
117 alpm_graph_t
*v_i
= i
->data
;
119 if(v_i
->state
== -1) {
123 if(v
== NULL
|| v_i
->weight
< v
->weight
) {
127 if(v
== NULL
|| v
->weight
== LONG_MAX
) {
133 v
->childptr
= v
->children
;
135 alpm_graph_t
*v_c
= v
->childptr
->data
;
136 alpm_delta_t
*d_c
= v_c
->data
;
137 if(v_c
->weight
> v
->weight
+ d_c
->download_size
) {
138 v_c
->weight
= v
->weight
+ d_c
->download_size
;
142 v
->childptr
= (v
->childptr
)->next
;
148 static off_t
shortest_path(alpm_list_t
*vertices
, const char *to
, alpm_list_t
**path
)
151 alpm_graph_t
*v
= NULL
;
153 alpm_list_t
*rpath
= NULL
;
155 for(i
= vertices
; i
; i
= i
->next
) {
156 alpm_graph_t
*v_i
= i
->data
;
157 alpm_delta_t
*d_i
= v_i
->data
;
159 if(strcmp(d_i
->to
, to
) == 0) {
160 if(v
== NULL
|| v_i
->weight
< v
->weight
) {
162 bestsize
= v
->weight
;
168 alpm_delta_t
*vdelta
= v
->data
;
169 rpath
= alpm_list_add(rpath
, vdelta
);
172 *path
= alpm_list_reverse(rpath
);
173 alpm_list_free(rpath
);
178 /** Calculates the shortest path from one version to another.
179 * The shortest path is defined as the path with the smallest combined
180 * size, not the length of the path.
181 * @param handle the context handle
182 * @param deltas the list of alpm_delta_t * objects that a file has
183 * @param to the file to start the search at
184 * @param path the pointer to a list location where alpm_delta_t * objects that
185 * have the smallest size are placed. NULL is set if there is no path
186 * possible with the files available.
187 * @return the size of the path stored, or LONG_MAX if path is unfindable
189 off_t
_alpm_shortest_delta_path(alpm_handle_t
*handle
, alpm_list_t
*deltas
,
190 const char *to
, alpm_list_t
**path
)
192 alpm_list_t
*bestpath
= NULL
;
193 alpm_list_t
*vertices
;
194 off_t bestsize
= LONG_MAX
;
201 _alpm_log(handle
, PM_LOG_DEBUG
, "started delta shortest-path search for '%s'\n", to
);
203 vertices
= graph_init(deltas
, 0);
204 graph_init_size(handle
, vertices
);
206 bestsize
= shortest_path(vertices
, to
, &bestpath
);
208 _alpm_log(handle
, PM_LOG_DEBUG
, "delta shortest-path search complete : '%jd'\n", (intmax_t)bestsize
);
210 alpm_list_free_inner(vertices
, _alpm_graph_free
);
211 alpm_list_free(vertices
);
217 static alpm_list_t
*find_unused(alpm_list_t
*deltas
, const char *to
, off_t quota
)
219 alpm_list_t
*unused
= NULL
;
220 alpm_list_t
*vertices
;
222 vertices
= graph_init(deltas
, 1);
224 for(i
= vertices
; i
; i
= i
->next
) {
225 alpm_graph_t
*v
= i
->data
;
226 alpm_delta_t
*vdelta
= v
->data
;
227 if(strcmp(vdelta
->to
, to
) == 0)
229 v
->weight
= vdelta
->download_size
;
233 for(i
= vertices
; i
; i
= i
->next
) {
234 alpm_graph_t
*v
= i
->data
;
235 alpm_delta_t
*vdelta
= v
->data
;
236 if(v
->weight
> quota
) {
237 unused
= alpm_list_add(unused
, vdelta
->delta
);
240 alpm_list_free_inner(vertices
, _alpm_graph_free
);
241 alpm_list_free(vertices
);
245 /** \addtogroup alpm_deltas Delta Functions
246 * @brief Functions to manipulate libalpm deltas
250 alpm_list_t SYMEXPORT
*alpm_pkg_unused_deltas(alpm_pkg_t
*pkg
)
252 off_t pkgsize
= alpm_pkg_get_size(pkg
);
253 alpm_list_t
*unused
= find_unused(
254 alpm_pkg_get_deltas(pkg
),
255 alpm_pkg_get_filename(pkg
),
256 pkgsize
* MAX_DELTA_RATIO
);
262 /** Parses the string representation of a alpm_delta_t object.
263 * This function assumes that the string is in the correct format.
264 * This format is as follows:
265 * $deltafile $deltamd5 $deltasize $oldfile $newfile
266 * @param line the string to parse
267 * @return A pointer to the new alpm_delta_t object
269 /* TODO this does not really belong here, but in a parsing lib */
270 alpm_delta_t
*_alpm_delta_parse(char *line
)
273 char *tmp
= line
, *tmp2
;
277 "^[^[:space:]]* [[:xdigit:]]{32} [[:digit:]]*"
278 " [^[:space:]]* [^[:space:]]*$",
279 REG_EXTENDED
| REG_NOSUB
| REG_NEWLINE
);
280 if(regexec(®
, line
, 0, 0, 0) != 0) {
281 /* delta line is invalid, return NULL */
287 CALLOC(delta
, 1, sizeof(alpm_delta_t
), return NULL
);
290 tmp
= strchr(tmp
, ' ');
292 STRDUP(delta
->delta
, tmp2
, return NULL
);
295 tmp
= strchr(tmp
, ' ');
297 STRDUP(delta
->delta_md5
, tmp2
, return NULL
);
300 tmp
= strchr(tmp
, ' ');
302 delta
->delta_size
= atol(tmp2
);
305 tmp
= strchr(tmp
, ' ');
307 STRDUP(delta
->from
, tmp2
, return NULL
);
310 STRDUP(delta
->to
, tmp2
, return NULL
);
315 void _alpm_delta_free(alpm_delta_t
*delta
)
318 FREE(delta
->delta_md5
);
324 alpm_delta_t
*_alpm_delta_dup(const alpm_delta_t
*delta
)
326 alpm_delta_t
*newdelta
;
327 CALLOC(newdelta
, 1, sizeof(alpm_delta_t
), return NULL
);
328 STRDUP(newdelta
->delta
, delta
->delta
, return NULL
);
329 STRDUP(newdelta
->delta_md5
, delta
->delta_md5
, return NULL
);
330 STRDUP(newdelta
->from
, delta
->from
, return NULL
);
331 STRDUP(newdelta
->to
, delta
->to
, return NULL
);
332 newdelta
->delta_size
= delta
->delta_size
;
333 newdelta
->download_size
= delta
->download_size
;
338 /* vim: set ts=2 sw=2 noet: */