[pacman-dev] [PATCH 2/4] Add pmdelta_t structure and functions to libalpm.

[Xavier]

On Mon, Oct 15, 2007 at 05:51:10PM -0400, Nathan Jones wrote:
> +/** 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 used is 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);
> +			newpath = alpm_list_add(newpath, v);
> +
> +			if((newpath = shortest_delta_path(deltas, v->to, to, newpath))) {
> +				/* 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;
> +}
> +

Is this really the Dijkstra algorithm?
Looks like it does repetitive computation to me.
Not that it really matters, given the very low values we work on. The only
thing that bothers me slightly is the reference to it, in case I'm not
mistaken.

In any cases, I found the code clear and well written, so good job :)