chiark - git - mdw - dpkg/blob - lib/dpkg/pkg-db.c

   1 /*
   2  * libdpkg - Debian packaging suite library routines
   3  * pkg-db.c - low level package database routines (hash tables, etc.)
   4  *
   5  * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk>
   6  * Copyright © 2008-2014 Guillem Jover <guillem@debian.org>
   7  * Copyright © 2011 Linaro Limited
   8  * Copyright © 2011 Raphaël Hertzog <hertzog@debian.org>
   9  *
  10  * This is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  22  */
  23
  24 #include <config.h>
  25 #include <compat.h>
  26
  27 #include <assert.h>
  28 #include <string.h>
  29 #include <stdlib.h>
  30
  31 #include <dpkg/i18n.h>
  32 #include <dpkg/c-ctype.h>
  33 #include <dpkg/dpkg.h>
  34 #include <dpkg/dpkg-db.h>
  35 #include <dpkg/string.h>
  36 #include <dpkg/arch.h>
  37
  38 /* This must always be a prime for optimal performance.
  39  * With 4093 buckets, we glean a 20% speedup, for 8191 buckets
  40  * we get 23%. The nominal increase in memory usage is a mere
  41  * sizeof(void *) * 8191 (i.e. less than 32 KiB on 32bit systems). */
  42 #define BINS 8191
  43
  44 static struct pkgset *bins[BINS];
  45 static int npkg, nset;
  46
  47 /**
  48  * Return the package set with the given name.
  49  *
  50  * If the package already exists in the internal database, then it returns
  51  * the existing structure. Otherwise it allocates a new one and will return
  52  * it. The actual name associated to the package set is a lowercase version
  53  * of the name given in parameter.
  54  *
  55  * A package set (struct pkgset) can be composed of multiple package instances
  56  * (struct pkginfo) where each instance is distinguished by its architecture
  57  * (as recorded in pkg.installed.arch and pkg.available.arch).
  58  *
  59  * @param inname Name of the package set.
  60  *
  61  * @return The package set.
  62  */
  63 struct pkgset *
  64 pkg_db_find_set(const char *inname)
  65 {
  66   struct pkgset **setp, *new_set;
  67   char *name = m_strdup(inname), *p;
  68
  69   p= name;
  70   while (*p) {
  71     *p = c_tolower(*p);
  72     p++;
  73   }
  74
  75   setp = bins + (str_fnv_hash(name) % (BINS));
  76   while (*setp && strcasecmp((*setp)->name, name))
  77     setp = &(*setp)->next;
  78   if (*setp) {
  79     free(name);
  80     return *setp;
  81   }
  82
  83   new_set = nfmalloc(sizeof(struct pkgset));
  84   pkgset_blank(new_set);
  85   new_set->name = nfstrsave(name);
  86   new_set->next = NULL;
  87   *setp = new_set;
  88   nset++;
  89   npkg++;
  90
  91   free(name);
  92
  93   return new_set;
  94 }
  95
  96 /**
  97  * Return the singleton package instance from a package set.
  98  *
  99  * This means, if none are installed either an instance with native or
 100  * all arch or the first if none found, the single installed instance,
 101  * or NULL if more than one instance is installed.
 102  *
 103  * @param set The package set to use.
 104  *
 105  * @return The singleton package instance.
 106  */
 107 struct pkginfo *
 108 pkg_db_get_singleton(struct pkgset *set)
 109 {
 110   struct pkginfo *pkg;
 111
 112   switch (pkgset_installed_instances(set)) {
 113   case 0:
 114     /* Pick an available candidate. */
 115     for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
 116       const struct dpkg_arch *arch = pkg->available.arch;
 117
 118       if (arch->type == DPKG_ARCH_NATIVE || arch->type == DPKG_ARCH_ALL)
 119         return pkg;
 120     }
 121     /* Or failing that, the first entry. */
 122     return &set->pkg;
 123   case 1:
 124     for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
 125       if (pkg->status > PKG_STAT_NOTINSTALLED)
 126         return pkg;
 127     }
 128     internerr("pkgset '%s' should have one installed instance", set->name);
 129   default:
 130     return NULL;
 131   }
 132 }
 133
 134 /**
 135  * Return the singleton package instance with the given name.
 136  *
 137  * @param name The package name.
 138  *
 139  * @return The package instance.
 140  */
 141 struct pkginfo *
 142 pkg_db_find_singleton(const char *name)
 143 {
 144   struct pkgset *set;
 145   struct pkginfo *pkg;
 146
 147   set = pkg_db_find_set(name);
 148   pkg = pkg_db_get_singleton(set);
 149   if (pkg == NULL)
 150     ohshit(_("ambiguous package name '%s' with more "
 151              "than one installed instance"), set->name);
 152
 153   return pkg;
 154 }
 155
 156 /**
 157  * Return the package instance in a set with the given architecture.
 158  *
 159  * It traverse the various instances to find out whether there's one
 160  * matching the given architecture. If found, it returns it. Otherwise it
 161  * allocates a new instance and registers it in the package set before
 162  * returning it.
 163  *
 164  * @param set  The package set to use.
 165  * @param arch The requested architecture.
 166  *
 167  * @return The package instance.
 168  */
 169 struct pkginfo *
 170 pkg_db_get_pkg(struct pkgset *set, const struct dpkg_arch *arch)
 171 {
 172   struct pkginfo *pkg, **pkgp;
 173
 174   assert(arch);
 175   assert(arch->type != DPKG_ARCH_NONE);
 176
 177   pkg = &set->pkg;
 178
 179   /* If there's a single unused slot, let's use that. */
 180   if (pkg->installed.arch->type == DPKG_ARCH_NONE && pkg->arch_next == NULL) {
 181     pkg->installed.arch = arch;
 182     pkg->available.arch = arch;
 183     return pkg;
 184   }
 185
 186   /* Match the slot with the most appropriate architecture. The installed
 187    * architecture always has preference over the available one, as there's
 188    * a small time window on cross-grades, where they might differ. */
 189   for (pkgp = &pkg; *pkgp; pkgp = &(*pkgp)->arch_next) {
 190     if ((*pkgp)->installed.arch == arch)
 191       return *pkgp;
 192   }
 193
 194   /* Need to create a new instance for the wanted architecture. */
 195   pkg = nfmalloc(sizeof(struct pkginfo));
 196   pkg_blank(pkg);
 197   pkg->set = set;
 198   pkg->arch_next = NULL;
 199   pkg->installed.arch = arch;
 200   pkg->available.arch = arch;
 201   *pkgp = pkg;
 202   npkg++;
 203
 204   return pkg;
 205 }
 206
 207 /**
 208  * Return the package instance with the given name and architecture.
 209  *
 210  * @param name The package name.
 211  * @param arch The requested architecture.
 212  *
 213  * @return The package instance.
 214  */
 215 struct pkginfo *
 216 pkg_db_find_pkg(const char *name, const struct dpkg_arch *arch)
 217 {
 218   struct pkgset *set;
 219   struct pkginfo *pkg;
 220
 221   set = pkg_db_find_set(name);
 222   pkg = pkg_db_get_pkg(set, arch);
 223
 224   return pkg;
 225 }
 226
 227 /**
 228  * Return the number of package sets available in the database.
 229  *
 230  * @return The number of package sets.
 231  */
 232 int
 233 pkg_db_count_set(void)
 234 {
 235   return nset;
 236 }
 237
 238 /**
 239  * Return the number of package instances available in the database.
 240  *
 241  * @return The number of package instances.
 242  */
 243 int
 244 pkg_db_count_pkg(void)
 245 {
 246   return npkg;
 247 }
 248
 249 struct pkgiterator {
 250   struct pkginfo *pkg;
 251   int nbinn;
 252 };
 253
 254 /**
 255  * Create a new package iterator.
 256  *
 257  * It can iterate either over package sets or over package instances.
 258  *
 259  * @return The iterator.
 260  */
 261 struct pkgiterator *
 262 pkg_db_iter_new(void)
 263 {
 264   struct pkgiterator *iter;
 265
 266   iter = m_malloc(sizeof(struct pkgiterator));
 267   iter->pkg = NULL;
 268   iter->nbinn = 0;
 269
 270   return iter;
 271 }
 272
 273 /**
 274  * Return the next package set in the database.
 275  *
 276  * If no further package set is available, it will return NULL.
 277  *
 278  * @name iter The iterator.
 279  *
 280  * @return A package set.
 281  */
 282 struct pkgset *
 283 pkg_db_iter_next_set(struct pkgiterator *iter)
 284 {
 285   struct pkgset *set;
 286
 287   while (!iter->pkg) {
 288     if (iter->nbinn >= BINS)
 289       return NULL;
 290     if (bins[iter->nbinn])
 291       iter->pkg = &bins[iter->nbinn]->pkg;
 292     iter->nbinn++;
 293   }
 294
 295   set = iter->pkg->set;
 296   if (set->next)
 297     iter->pkg = &set->next->pkg;
 298   else
 299     iter->pkg = NULL;
 300
 301   return set;
 302 }
 303
 304 /**
 305  * Return the next package instance in the database.
 306  *
 307  * If no further package instance is available, it will return NULL. Note
 308  * that it will return all instances of a given package set in sequential
 309  * order. The first instance for a given package set will always correspond
 310  * to the native architecture even if that package is not installed or
 311  * available.
 312  *
 313  * @name iter The iterator.
 314  *
 315  * @return A package instance.
 316  */
 317 struct pkginfo *
 318 pkg_db_iter_next_pkg(struct pkgiterator *iter)
 319 {
 320   struct pkginfo *pkg;
 321
 322   while (!iter->pkg) {
 323     if (iter->nbinn >= BINS)
 324       return NULL;
 325     if (bins[iter->nbinn])
 326       iter->pkg = &bins[iter->nbinn]->pkg;
 327     iter->nbinn++;
 328   }
 329
 330   pkg = iter->pkg;
 331   if (pkg->arch_next)
 332     iter->pkg = pkg->arch_next;
 333   else if (pkg->set->next)
 334     iter->pkg = &pkg->set->next->pkg;
 335   else
 336     iter->pkg = NULL;
 337
 338   return pkg;
 339 }
 340
 341 /**
 342  * Free the package database iterator.
 343  *
 344  * @name iter The iterator.
 345  */
 346 void
 347 pkg_db_iter_free(struct pkgiterator *iter)
 348 {
 349   free(iter);
 350 }
 351
 352 void
 353 pkg_db_reset(void)
 354 {
 355   int i;
 356
 357   dpkg_arch_reset_list();
 358   nffreeall();
 359   nset = 0;
 360   npkg = 0;
 361   for (i=0; i<BINS; i++) bins[i]= NULL;
 362 }
 363
 364 void
 365 pkg_db_report(FILE *file)
 366 {
 367   int i, c;
 368   struct pkgset *pkg;
 369   int *freq;
 370
 371   freq = m_malloc(sizeof(int) * nset + 1);
 372   for (i = 0; i <= nset; i++)
 373     freq[i] = 0;
 374   for (i=0; i<BINS; i++) {
 375     for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next);
 376     fprintf(file,"bin %5d has %7d\n",i,c);
 377     freq[c]++;
 378   }
 379   for (i = nset; i > 0 && freq[i] == 0; i--);
 380   while (i >= 0) {
 381     fprintf(file, "size %7d occurs %5d times\n", i, freq[i]);
 382     i--;
 383   }
 384
 385   m_output(file, "<hash report>");
 386
 387   free(freq);
 388 }