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

Dan McGee dpmcgee at gmail.com
Mon Oct 15 22:38:39 EDT 2007


On 10/15/07, Nathan Jones <nathanj at insightbb.com> wrote:
> Signed-off-by: Nathan Jones <nathanj at insightbb.com>
> ---
>  lib/libalpm/Makefile.am |    1 +
>  lib/libalpm/alpm.h      |   13 +++
>  lib/libalpm/alpm_list.c |   18 ++++
>  lib/libalpm/alpm_list.h |    1 +
>  lib/libalpm/be_files.c  |   19 ++++
>  lib/libalpm/db.h        |    3 +-
>  lib/libalpm/delta.c     |  249 +++++++++++++++++++++++++++++++++++++++++++++++
>  lib/libalpm/delta.h     |   44 ++++++++
>  lib/libalpm/package.c   |   15 +++
>  lib/libalpm/package.h   |    1 +
>  10 files changed, 363 insertions(+), 1 deletions(-)
>  create mode 100644 lib/libalpm/delta.c
>  create mode 100644 lib/libalpm/delta.h
>
> diff --git a/lib/libalpm/Makefile.am b/lib/libalpm/Makefile.am
> index 6948239..49ce14c 100644
> --- a/lib/libalpm/Makefile.am
> +++ b/lib/libalpm/Makefile.am
> @@ -18,6 +18,7 @@ libalpm_la_SOURCES = \
>         cache.h cache.c \
>         conflict.h conflict.c \
>         db.h db.c \
> +       delta.h delta.c \
>         deps.h deps.c \
>         error.h error.c \
>         group.h group.c \

Glad you caught this, but can you add the two files to
libalpm/po/POTFILES.in as well?

> diff --git a/lib/libalpm/alpm.h b/lib/libalpm/alpm.h
> index 6eda210..527822d 100644
> --- a/lib/libalpm/alpm.h
> +++ b/lib/libalpm/alpm.h
> @@ -45,6 +45,7 @@ extern "C" {
>
>  typedef struct __pmdb_t pmdb_t;
>  typedef struct __pmpkg_t pmpkg_t;
> +typedef struct __pmdelta_t pmdelta_t;
>  typedef struct __pmgrp_t pmgrp_t;
>  typedef struct __pmserver_t pmserver_t;
>  typedef struct __pmtrans_t pmtrans_t;
> @@ -207,12 +208,24 @@ alpm_list_t *alpm_pkg_get_optdepends(pmpkg_t *pkg);
>  alpm_list_t *alpm_pkg_get_requiredby(pmpkg_t *pkg);
>  alpm_list_t *alpm_pkg_get_conflicts(pmpkg_t *pkg);
>  alpm_list_t *alpm_pkg_get_provides(pmpkg_t *pkg);
> +alpm_list_t *alpm_pkg_get_deltas(pmpkg_t *pkg);
>  alpm_list_t *alpm_pkg_get_replaces(pmpkg_t *pkg);
>  alpm_list_t *alpm_pkg_get_files(pmpkg_t *pkg);
>  alpm_list_t *alpm_pkg_get_backup(pmpkg_t *pkg);
>  unsigned short alpm_pkg_has_scriptlet(pmpkg_t *pkg);
>
>  /*
> + * Deltas
> + */
> +
> +char *alpm_delta_get_from(pmdelta_t *delta);
> +char *alpm_delta_get_to(pmdelta_t *delta);
> +unsigned long alpm_delta_get_size(pmdelta_t *delta);
> +char *alpm_delta_get_filename(pmdelta_t *delta);
> +char *alpm_delta_get_md5sum(pmdelta_t *delta);
> +alpm_list_t *alpm_shortest_delta_path(alpm_list_t *deltas, const char *from, const char *to);
> +
> +/*
>   * Groups
>   */
>  const char *alpm_grp_get_name(const pmgrp_t *grp);
> diff --git a/lib/libalpm/alpm_list.c b/lib/libalpm/alpm_list.c
> index 5671b4a..2301411 100644
> --- a/lib/libalpm/alpm_list.c
> +++ b/lib/libalpm/alpm_list.c
> @@ -379,6 +379,24 @@ alpm_list_t SYMEXPORT *alpm_list_strdup(const alpm_list_t *list)
>  }
>
>  /**
> + * @brief Copy a list, without copying data.
> + *
> + * @param list the list to copy
> + *
> + * @return a copy of the original list
> + */
> +alpm_list_t SYMEXPORT *alpm_list_copy(const alpm_list_t *list)
> +{
> +       const alpm_list_t *lp = list;
> +       alpm_list_t *newlist = NULL;
> +       while(lp) {
> +               newlist = alpm_list_add(newlist, lp->data);
> +               lp = lp->next;
> +       }
> +       return(newlist);
> +}
> +
> +/**
>   * @brief Create a new list in reverse order.
>   *
>   * @param list the list to copy
> diff --git a/lib/libalpm/alpm_list.h b/lib/libalpm/alpm_list.h
> index a2a06f4..8fce280 100644
> --- a/lib/libalpm/alpm_list.h
> +++ b/lib/libalpm/alpm_list.h
> @@ -60,6 +60,7 @@ alpm_list_t *alpm_list_remove(alpm_list_t *haystack, const void *needle, alpm_li
>  alpm_list_t *alpm_list_remove_node(alpm_list_t *node);
>  alpm_list_t *alpm_list_remove_dupes(const alpm_list_t *list);
>  alpm_list_t *alpm_list_strdup(const alpm_list_t *list);
> +alpm_list_t *alpm_list_copy(const alpm_list_t *list);
>  alpm_list_t *alpm_list_reverse(alpm_list_t *list);
>
>  /* item accessors */
> diff --git a/lib/libalpm/be_files.c b/lib/libalpm/be_files.c
> index 2bfdb95..59155cf 100644
> --- a/lib/libalpm/be_files.c
> +++ b/lib/libalpm/be_files.c
> @@ -44,6 +44,7 @@
>  #include "error.h"
>  #include "handle.h"
>  #include "package.h"
> +#include "delta.h"
>
>
>  /* This function is used to convert the downloaded db file to the proper backend
> @@ -484,6 +485,24 @@ int _alpm_db_read(pmdb_t *db, pmpkg_t *info, pmdbinfrq_t inforeq)
>                 fp = NULL;
>         }
>
> +       /* DELTAS */
> +       if(inforeq & INFRQ_DELTAS) {
> +               snprintf(path, PATH_MAX, "%s/%s-%s/deltas", db->path, info->name, info->version);
> +               if((fp = fopen(path, "r"))) {
> +                       while(!feof(fp)) {
> +                               fgets(line, 255, fp);
> +                               _alpm_strtrim(line);
> +                               if(!strcmp(line, "%DELTAS%")) {
> +                                       while(fgets(line, 512, fp) && strlen(_alpm_strtrim(line))) {
> +                                               info->deltas = alpm_list_add(info->deltas, _alpm_delta_parse(line));
> +                                       }
> +                               }
> +                       }
> +                       fclose(fp);
> +                       fp = NULL;
> +               }
> +       }
> +
>         /* INSTALL */
>         if(inforeq & INFRQ_SCRIPTLET) {
>                 snprintf(path, PATH_MAX, "%s/%s-%s/install", db->path, info->name, info->version);
> diff --git a/lib/libalpm/db.h b/lib/libalpm/db.h
> index 3ee4977..16e1298 100644
> --- a/lib/libalpm/db.h
> +++ b/lib/libalpm/db.h
> @@ -33,8 +33,9 @@ typedef enum _pmdbinfrq_t {
>         INFRQ_DEPENDS = 0x04,
>         INFRQ_FILES = 0x08,
>         INFRQ_SCRIPTLET = 0x10,
> +       INFRQ_DELTAS = 0x20,
>         /* ALL should be sum of all above */
> -       INFRQ_ALL = 0x1F
> +       INFRQ_ALL = 0x3F
>  } pmdbinfrq_t;
>
>  /* Database */
> diff --git a/lib/libalpm/delta.c b/lib/libalpm/delta.c
> new file mode 100644
> index 0000000..1760a3c
> --- /dev/null
> +++ b/lib/libalpm/delta.c
> @@ -0,0 +1,249 @@
> +/*
> + *  delta.c
> + *
> + *  Copyright (c) 2002-2006 by Judd Vinet <jvinet at zeroflux.org>
> + *  Copyright (c) 2005 by Aurelien Foret <orelien at chez.com>
> + *  Copyright (c) 2005, 2006 by Christian Hamar <krics at linuxforum.hu>
> + *  Copyright (c) 2005, 2006 by Miklos Vajna <vmiklos at frugalware.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, write to the Free Software
> + *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
> + *  USA.
> + */
> +
> +#include "config.h"
> +
> +#include <stdlib.h>
> +#include <string.h>
> +
> +/* libalpm */
> +#include "delta.h"
> +#include "util.h"
> +#include "log.h"
> +#include "alpm_list.h"
> +#include "alpm.h"
> +
> +/** \addtogroup alpm_deltas Delta Functions
> + * @brief Functions to manipulate libalpm deltas
> + * @{
> + */
> +
> +char SYMEXPORT *alpm_delta_get_from(pmdelta_t *delta)
> +{
> +       ALPM_LOG_FUNC;
> +
> +       return delta->from;
> +}
> +
> +char SYMEXPORT *alpm_delta_get_to(pmdelta_t *delta)
> +{
> +       ALPM_LOG_FUNC;
> +
> +       return delta->to;
> +}
> +
> +unsigned long SYMEXPORT alpm_delta_get_size(pmdelta_t *delta)
> +{
> +       ALPM_LOG_FUNC;
> +
> +       return delta->size;
> +}
> +
> +char SYMEXPORT *alpm_delta_get_filename(pmdelta_t *delta)
> +{
> +       ALPM_LOG_FUNC;
> +
> +       return delta->filename;
> +}
> +
> +char SYMEXPORT *alpm_delta_get_md5sum(pmdelta_t *delta)
> +{
> +       ALPM_LOG_FUNC;
> +
> +       return delta->md5sum;
> +}
> +
> +/** @} */
> +
> +/** Calculates the combined size of a list of delta files.
> + *
> + * @param deltas the list of pmdelta_t * objects
> + *
> + * @return the combined size
> + */
> +unsigned long _alpm_delta_path_size(alpm_list_t *deltas)
> +{
> +       unsigned long sum = 0;
> +       alpm_list_t *dlts = deltas;
> +
> +       while(dlts) {
> +               pmdelta_t *d = (pmdelta_t *)alpm_list_getdata(dlts);
> +               sum += d->size;
> +
> +               dlts = alpm_list_next(dlts);
> +       }
> +
> +       return sum;
> +}
> +
> +/** Calculates the combined size of a list of delta files that are not
> + * in the cache.
> + *
> + * @param deltas the list of pmdelta_t * objects
> + *
> + * @return the combined size
> + */
> +unsigned long _alpm_delta_path_size_uncached(alpm_list_t *deltas)
> +{
> +       unsigned long sum = 0;
> +       alpm_list_t *dlts = deltas;
> +
> +       while(dlts) {
> +               pmdelta_t *d = (pmdelta_t *)alpm_list_getdata(dlts);
> +               char *fname = _alpm_filecache_find(d->filename);
> +
> +               if(!fname) {
> +                       sum += d->size;
> +               }
> +
> +               FREE(fname);
> +
> +               dlts = alpm_list_next(dlts);
> +       }
> +
> +       return sum;
> +}
> +
> +/** 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;
> +}
> +
> +/** 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 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
> + *
> + * @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.
> + */
> +alpm_list_t SYMEXPORT *alpm_shortest_delta_path(alpm_list_t *deltas, const char *from, const char *to)
> +{
> +       alpm_list_t *path = NULL;
> +
> +       path = shortest_delta_path(deltas, from, to, path);
> +
> +       return path;
> +}
> +
> +/** Parses the string representation of a pmdelta_t object.
> + *
> + * This function assumes that the string is in the correct format.
> + *
> + * @param line the string to parse
> + *
> + * @return A pointer to the new pmdelta_t object
> + */
> +pmdelta_t *_alpm_delta_parse(char *line)
> +{
> +       pmdelta_t *delta;
> +       char *tmp = line, *tmp2;
> +
> +       delta = malloc(sizeof(pmdelta_t));
> +
> +       tmp2 = tmp;
> +       tmp = strchr(tmp, ' ');
> +       *(tmp++) = '\0';
> +       delta->from = strdup(tmp2);
> +
> +       tmp2 = tmp;
> +       tmp = strchr(tmp, ' ');
> +       *(tmp++) = '\0';
> +       delta->to = strdup(tmp2);
> +
> +       tmp2 = tmp;
> +       tmp = strchr(tmp, ' ');
> +       *(tmp++) = '\0';
> +       delta->size = atol(tmp2);
> +
> +       tmp2 = tmp;
> +       tmp = strchr(tmp, ' ');
> +       *(tmp++) = '\0';
> +       delta->filename = strdup(tmp2);
> +
> +       delta->md5sum = strdup(tmp);
> +
> +       return delta;
> +}
> +
> +/* vim: set ts=2 sw=2 noet: */
> diff --git a/lib/libalpm/delta.h b/lib/libalpm/delta.h
> new file mode 100644
> index 0000000..4655d7a
> --- /dev/null
> +++ b/lib/libalpm/delta.h
> @@ -0,0 +1,44 @@
> +/*
> + *  delta.h
> + *
> + *  Copyright (c) 2002-2006 by Judd Vinet <jvinet at zeroflux.org>
> + *  Copyright (c) 2005 by Aurelien Foret <orelien at chez.com>
> + *  Copyright (c) 2006 by David Kimpe <dnaku at frugalware.org>
> + *  Copyright (c) 2005, 2006 by Christian Hamar <krics at linuxforum.hu>
> + *  Copyright (c) 2005, 2006 by Miklos Vajna <vmiklos at frugalware.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, write to the Free Software
> + *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
> + *  USA.
> + */
> +#ifndef _ALPM_DELTA_H
> +#define _ALPM_DELTA_H
> +
> +#include "alpm.h"
> +
> +struct __pmdelta_t {
> +       char *from;
> +       char *to;
> +       unsigned long size;
> +       char *filename;
> +       char *md5sum;
> +};
> +
> +unsigned long _alpm_delta_path_size(alpm_list_t *deltas);
> +unsigned long _alpm_delta_path_size_uncached(alpm_list_t *deltas);
> +pmdelta_t *_alpm_delta_parse(char *line);
> +
> +#endif /* _ALPM_DELTA_H */
> +
> +/* vim: set ts=2 sw=2 noet: */
> diff --git a/lib/libalpm/package.c b/lib/libalpm/package.c
> index 38e6e4c..6a8e0d8 100644
> --- a/lib/libalpm/package.c
> +++ b/lib/libalpm/package.c
> @@ -446,6 +446,20 @@ alpm_list_t SYMEXPORT *alpm_pkg_get_provides(pmpkg_t *pkg)
>         return pkg->provides;
>  }
>
> +alpm_list_t SYMEXPORT *alpm_pkg_get_deltas(pmpkg_t *pkg)
> +{
> +       ALPM_LOG_FUNC;
> +
> +       /* Sanity checks */
> +       ASSERT(handle != NULL, return(NULL));
> +       ASSERT(pkg != NULL, return(NULL));
> +
> +       if(pkg->origin == PKG_FROM_CACHE && !(pkg->infolevel & INFRQ_DELTAS)) {
> +               _alpm_db_read(pkg->origin_data.db, pkg, INFRQ_DELTAS);
> +       }
> +       return pkg->deltas;
> +}
> +
>  alpm_list_t SYMEXPORT *alpm_pkg_get_replaces(pmpkg_t *pkg)
>  {
>         ALPM_LOG_FUNC;
> @@ -725,6 +739,7 @@ void _alpm_pkg_free(pmpkg_t *pkg)
>         FREELIST(pkg->groups);
>         FREELIST(pkg->provides);
>         FREELIST(pkg->replaces);
> +       FREELIST(pkg->deltas);
>         if(pkg->origin == PKG_FROM_FILE) {
>                 FREE(pkg->origin_data.file);
>         }
> diff --git a/lib/libalpm/package.h b/lib/libalpm/package.h
> index 42ebe0e..daaeb36 100644
> --- a/lib/libalpm/package.h
> +++ b/lib/libalpm/package.h
> @@ -75,6 +75,7 @@ struct __pmpkg_t {
>         alpm_list_t *requiredby;
>         alpm_list_t *conflicts;
>         alpm_list_t *provides;
> +       alpm_list_t *deltas;
>         /* internal */
>         pmpkgfrom_t origin;
>         /* Replaced 'void *data' with this union as follows:
> --
> 1.5.3.4

Wow, I'm impressed here. Great job.

-Dan




More information about the pacman-dev mailing list