summaryrefslogtreecommitdiff
path: root/lib/libalpm/delta.c
blob: c5770bfc48a4ec4d130bf28e41e14286f381add6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
/*
 *  delta.c
 *
 *  Copyright (c) 2006-2011 Pacman Development Team <pacman-dev@archlinux.org>
 *  Copyright (c) 2007-2006 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, see <http://www.gnu.org/licenses/>.
 */

#include "config.h"

#include <stdlib.h>
#include <string.h>
#include <stdint.h> /* intmax_t */
#include <limits.h>
#include <sys/types.h>
#include <regex.h>

/* libalpm */
#include "delta.h"
#include "alpm_list.h"
#include "util.h"
#include "log.h"
#include "graph.h"

static alpm_list_t *graph_init(alpm_list_t *deltas, int reverse)
{
	alpm_list_t *i, *j;
	alpm_list_t *vertices = NULL;
	/* create the vertices */
	for(i = deltas; i; i = i->next) {
		pmgraph_t *v = _alpm_graph_new();
		if(!v) {
			alpm_list_free(vertices);
			return NULL;
		}
		alpm_delta_t *vdelta = i->data;
		vdelta->download_size = vdelta->delta_size;
		v->weight = LONG_MAX;
		v->data = vdelta;
		vertices = alpm_list_add(vertices, v);
	}

	/* compute the edges */
	for(i = vertices; i; i = i->next) {
		pmgraph_t *v_i = i->data;
		alpm_delta_t *d_i = v_i->data;
		/* loop a second time so we make all possible comparisons */
		for(j = vertices; j; j = j->next) {
			pmgraph_t *v_j = j->data;
			alpm_delta_t *d_j = v_j->data;
			/* We want to create a delta tree like the following:
			 *          1_to_2
			 *            |
			 * 1_to_3   2_to_3
			 *   \        /
			 *     3_to_4
			 * If J 'from' is equal to I 'to', then J is a child of I.
			 * */
			if((!reverse && strcmp(d_j->from, d_i->to) == 0) ||
					(reverse && strcmp(d_j->to, d_i->from) == 0)) {
				v_i->children = alpm_list_add(v_i->children, v_j);
			}
		}
		v_i->childptr = v_i->children;
	}
	return vertices;
}

static void graph_init_size(alpm_handle_t *handle, alpm_list_t *vertices)
{
	alpm_list_t *i;

	for(i = vertices; i; i = i->next) {
		char *fpath, *md5sum;
		pmgraph_t *v = i->data;
		alpm_delta_t *vdelta = v->data;

		/* determine whether the delta file already exists */
		fpath = _alpm_filecache_find(handle, vdelta->delta);
		md5sum = alpm_compute_md5sum(fpath);
		if(fpath && md5sum && strcmp(md5sum, vdelta->delta_md5) == 0) {
			vdelta->download_size = 0;
		}
		FREE(fpath);
		FREE(md5sum);

		/* determine whether a base 'from' file exists */
		fpath = _alpm_filecache_find(handle, vdelta->from);
		if(fpath) {
			v->weight = vdelta->download_size;
		}
		FREE(fpath);
	}
}


static void dijkstra(alpm_list_t *vertices)
{
	alpm_list_t *i;
	pmgraph_t *v;
	while(1) {
		v = NULL;
		/* find the smallest vertice not visited yet */
		for(i = vertices; i; i = i->next) {
			pmgraph_t *v_i = i->data;

			if(v_i->state == -1) {
				continue;
			}

			if(v == NULL || v_i->weight < v->weight) {
				v = v_i;
			}
		}
		if(v == NULL || v->weight == LONG_MAX) {
			break;
		}

		v->state = -1;

		v->childptr = v->children;
		while(v->childptr) {
			pmgraph_t *v_c = v->childptr->data;
			alpm_delta_t *d_c = v_c->data;
			if(v_c->weight > v->weight + d_c->download_size) {
				v_c->weight = v->weight + d_c->download_size;
				v_c->parent = v;
			}

			v->childptr = (v->childptr)->next;

		}
	}
}

static off_t shortest_path(alpm_list_t *vertices, const char *to, alpm_list_t **path)
{
	alpm_list_t *i;
	pmgraph_t *v = NULL;
	off_t bestsize = 0;
	alpm_list_t *rpath = NULL;

	for(i = vertices; i; i = i->next) {
		pmgraph_t *v_i = i->data;
		alpm_delta_t *d_i = v_i->data;

		if(strcmp(d_i->to, to) == 0) {
			if(v == NULL || v_i->weight < v->weight) {
				v = v_i;
				bestsize = v->weight;
			}
		}
	}

	while(v != NULL) {
		alpm_delta_t *vdelta = v->data;
		rpath = alpm_list_add(rpath, vdelta);
		v = v->parent;
	}
	*path = alpm_list_reverse(rpath);
	alpm_list_free(rpath);

	return bestsize;
}

/** 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 handle the context handle
 * @param deltas the list of alpm_delta_t * objects that a file has
 * @param to the file to start the search at
 * @param path the pointer to a list location where alpm_delta_t * objects that
 * have the smallest size are placed. NULL is set if there is no path
 * possible with the files available.
 * @return the size of the path stored, or LONG_MAX if path is unfindable
 */
off_t _alpm_shortest_delta_path(alpm_handle_t *handle, alpm_list_t *deltas,
		const char *to, alpm_list_t **path)
{
	alpm_list_t *bestpath = NULL;
	alpm_list_t *vertices;
	off_t bestsize = LONG_MAX;

	if(deltas == NULL) {
		*path = NULL;
		return bestsize;
	}

	_alpm_log(handle, PM_LOG_DEBUG, "started delta shortest-path search for '%s'\n", to);

	vertices = graph_init(deltas, 0);
	graph_init_size(handle, vertices);
	dijkstra(vertices);
	bestsize = shortest_path(vertices, to, &bestpath);

	_alpm_log(handle, PM_LOG_DEBUG, "delta shortest-path search complete : '%jd'\n", (intmax_t)bestsize);

	alpm_list_free_inner(vertices, _alpm_graph_free);
	alpm_list_free(vertices);

	*path = bestpath;
	return bestsize;
}

static alpm_list_t *find_unused(alpm_list_t *deltas, const char *to, off_t quota)
{
	alpm_list_t *unused = NULL;
	alpm_list_t *vertices;
	alpm_list_t *i;
	vertices = graph_init(deltas, 1);

	for(i = vertices; i; i = i->next) {
		pmgraph_t *v = i->data;
		alpm_delta_t *vdelta = v->data;
		if(strcmp(vdelta->to, to) == 0)
		{
			v->weight = vdelta->download_size;
		}
	}
	dijkstra(vertices);
	for(i = vertices; i; i = i->next) {
		pmgraph_t *v = i->data;
		alpm_delta_t *vdelta = v->data;
		if(v->weight > quota) {
			unused = alpm_list_add(unused, vdelta->delta);
		}
	}
	alpm_list_free_inner(vertices, _alpm_graph_free);
	alpm_list_free(vertices);
	return unused;
}

/** \addtogroup alpm_deltas Delta Functions
 * @brief Functions to manipulate libalpm deltas
 * @{
 */

alpm_list_t SYMEXPORT *alpm_pkg_unused_deltas(alpm_pkg_t *pkg)
{
	off_t pkgsize = alpm_pkg_get_size(pkg);
	alpm_list_t *unused = find_unused(
			alpm_pkg_get_deltas(pkg),
			alpm_pkg_get_filename(pkg),
			pkgsize * MAX_DELTA_RATIO);
	return unused;
}

/** @} */

/** Parses the string representation of a alpm_delta_t object.
 * This function assumes that the string is in the correct format.
 * This format is as follows:
 * $deltafile $deltamd5 $deltasize $oldfile $newfile
 * @param line the string to parse
 * @return A pointer to the new alpm_delta_t object
 */
/* TODO this does not really belong here, but in a parsing lib */
alpm_delta_t *_alpm_delta_parse(char *line)
{
	alpm_delta_t *delta;
	char *tmp = line, *tmp2;
	regex_t reg;

	regcomp(&reg,
			"^[^[:space:]]* [[:xdigit:]]{32} [[:digit:]]*"
			" [^[:space:]]* [^[:space:]]*$",
			REG_EXTENDED | REG_NOSUB | REG_NEWLINE);
	if(regexec(&reg, line, 0, 0, 0) != 0) {
		/* delta line is invalid, return NULL */
		regfree(&reg);
		return NULL;
	}
	regfree(&reg);

	CALLOC(delta, 1, sizeof(alpm_delta_t), return NULL);

	tmp2 = tmp;
	tmp = strchr(tmp, ' ');
	*(tmp++) = '\0';
	STRDUP(delta->delta, tmp2, return NULL);

	tmp2 = tmp;
	tmp = strchr(tmp, ' ');
	*(tmp++) = '\0';
	STRDUP(delta->delta_md5, tmp2, return NULL);

	tmp2 = tmp;
	tmp = strchr(tmp, ' ');
	*(tmp++) = '\0';
	delta->delta_size = atol(tmp2);

	tmp2 = tmp;
	tmp = strchr(tmp, ' ');
	*(tmp++) = '\0';
	STRDUP(delta->from, tmp2, return NULL);

	tmp2 = tmp;
	STRDUP(delta->to, tmp2, return NULL);

	return delta;
}

void _alpm_delta_free(alpm_delta_t *delta)
{
	FREE(delta->delta);
	FREE(delta->delta_md5);
	FREE(delta->from);
	FREE(delta->to);
	FREE(delta);
}

alpm_delta_t *_alpm_delta_dup(const alpm_delta_t *delta)
{
	alpm_delta_t *newdelta;
	CALLOC(newdelta, 1, sizeof(alpm_delta_t), return NULL);
	STRDUP(newdelta->delta, delta->delta, return NULL);
	STRDUP(newdelta->delta_md5, delta->delta_md5, return NULL);
	STRDUP(newdelta->from, delta->from, return NULL);
	STRDUP(newdelta->to, delta->to, return NULL);
	newdelta->delta_size = delta->delta_size;
	newdelta->download_size = delta->download_size;

	return newdelta;
}

/* vim: set ts=2 sw=2 noet: */