diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 14:58:51 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 14:58:51 +0000 |
commit | cbffab246997fb5a06211dfb706b54e5ae5bb59f (patch) | |
tree | 0573c5d96f58d74d76a49c0f2a70398e389a36d3 /lib/dpkg/pkg-hash.c | |
parent | Initial commit. (diff) | |
download | dpkg-cbffab246997fb5a06211dfb706b54e5ae5bb59f.tar.xz dpkg-cbffab246997fb5a06211dfb706b54e5ae5bb59f.zip |
Adding upstream version 1.21.22.upstream/1.21.22upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'lib/dpkg/pkg-hash.c')
-rw-r--r-- | lib/dpkg/pkg-hash.c | 407 |
1 files changed, 407 insertions, 0 deletions
diff --git a/lib/dpkg/pkg-hash.c b/lib/dpkg/pkg-hash.c new file mode 100644 index 0000000..6b0d337 --- /dev/null +++ b/lib/dpkg/pkg-hash.c @@ -0,0 +1,407 @@ +/* + * libdpkg - Debian packaging suite library routines + * pkg-hash.c - low level package database routines (hash tables, etc.) + * + * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk> + * Copyright © 2008-2014 Guillem Jover <guillem@debian.org> + * Copyright © 2011 Linaro Limited + * Copyright © 2011 Raphaël Hertzog <hertzog@debian.org> + * + * This 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 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 <https://www.gnu.org/licenses/>. + */ + +#include <config.h> +#include <compat.h> + +#include <string.h> +#include <stdlib.h> + +#include <dpkg/i18n.h> +#include <dpkg/c-ctype.h> +#include <dpkg/dpkg.h> +#include <dpkg/dpkg-db.h> +#include <dpkg/string.h> +#include <dpkg/arch.h> + +/* + * This must always be a prime for optimal performance. + * + * We use a number that is close to the amount of packages currently present + * in a Debian suite, so that installed and available packages do not add + * tons of collisions. + * + * The memory usage is «BINS * sizeof(void *)». + */ +#define BINS 65521 + +static struct pkgset *bins[BINS]; +static int npkg, nset; + +/** + * Return the package set with the given name. + * + * If the package already exists in the internal database, then it returns + * the existing structure. Otherwise it allocates a new one and will return + * it. The actual name associated to the package set is a lowercase version + * of the name given in parameter. + * + * A package set (struct pkgset) can be composed of multiple package instances + * (struct pkginfo) where each instance is distinguished by its architecture + * (as recorded in pkg.installed.arch and pkg.available.arch). + * + * @param inname Name of the package set. + * + * @return The package set. + */ +struct pkgset * +pkg_hash_find_set(const char *inname) +{ + struct pkgset **setp, *new_set; + char *name = m_strdup(inname), *p; + + p= name; + while (*p) { + *p = c_tolower(*p); + p++; + } + + setp = bins + (str_fnv_hash(name) % (BINS)); + while (*setp && strcasecmp((*setp)->name, name)) + setp = &(*setp)->next; + if (*setp) { + free(name); + return *setp; + } + + new_set = nfmalloc(sizeof(*new_set)); + pkgset_blank(new_set); + new_set->name = nfstrsave(name); + new_set->next = NULL; + *setp = new_set; + nset++; + npkg++; + + free(name); + + return new_set; +} + +/** + * Return the singleton package instance from a package set. + * + * This means, if none are installed either an instance with native or + * all arch or the first if none found, the single installed instance, + * or NULL if more than one instance is installed. + * + * @param set The package set to use. + * + * @return The singleton package instance. + */ +struct pkginfo * +pkg_hash_get_singleton(struct pkgset *set) +{ + struct pkginfo *pkg; + + switch (pkgset_installed_instances(set)) { + case 0: + /* Pick an available candidate. */ + for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) { + const struct dpkg_arch *arch = pkg->available.arch; + + if (arch->type == DPKG_ARCH_NATIVE || arch->type == DPKG_ARCH_ALL) + return pkg; + } + /* Or failing that, the first entry. */ + return &set->pkg; + case 1: + for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) { + if (pkg->status > PKG_STAT_NOTINSTALLED) + return pkg; + } + internerr("pkgset '%s' should have one installed instance", set->name); + default: + return NULL; + } +} + +/** + * Return the singleton package instance with the given name. + * + * @param name The package name. + * + * @return The package instance. + */ +struct pkginfo * +pkg_hash_find_singleton(const char *name) +{ + struct pkgset *set; + struct pkginfo *pkg; + + set = pkg_hash_find_set(name); + pkg = pkg_hash_get_singleton(set); + if (pkg == NULL) + ohshit(_("ambiguous package name '%s' with more " + "than one installed instance"), set->name); + + return pkg; +} + +/** + * Return the package instance in a set with the given architecture. + * + * It traverse the various instances to find out whether there's one + * matching the given architecture. If found, it returns it. Otherwise it + * allocates a new instance and registers it in the package set before + * returning it. + * + * @param set The package set to use. + * @param arch The requested architecture. + * + * @return The package instance. + */ +struct pkginfo * +pkg_hash_get_pkg(struct pkgset *set, const struct dpkg_arch *arch) +{ + struct pkginfo *pkg, **pkgp; + + if (arch == NULL) + internerr("arch argument is NULL"); + if (arch->type == DPKG_ARCH_NONE) + internerr("arch argument is none"); + + pkg = &set->pkg; + + /* If there's a single unused slot, let's use that. */ + if (pkg->installed.arch->type == DPKG_ARCH_NONE && pkg->arch_next == NULL) { + /* We can only initialize the arch pkgbin members, because those are used + * to find instances, anything else will be overwritten at parse time. */ + pkg->installed.arch = arch; + pkg->available.arch = arch; + return pkg; + } + + /* Match the slot with the most appropriate architecture. The installed + * architecture always has preference over the available one, as there's + * a small time window on cross-grades, where they might differ. */ + for (pkgp = &pkg; *pkgp; pkgp = &(*pkgp)->arch_next) { + if ((*pkgp)->installed.arch == arch) + return *pkgp; + } + + /* Need to create a new instance for the wanted architecture. */ + pkg = nfmalloc(sizeof(*pkg)); + pkg_blank(pkg); + pkg->set = set; + pkg->arch_next = NULL; + /* We can only initialize the arch pkgbin members, because those are used + * to find instances, anything else will be overwritten at parse time. */ + pkg->installed.arch = arch; + pkg->available.arch = arch; + *pkgp = pkg; + npkg++; + + return pkg; +} + +/** + * Return the package instance with the given name and architecture. + * + * @param name The package name. + * @param arch The requested architecture. + * + * @return The package instance. + */ +struct pkginfo * +pkg_hash_find_pkg(const char *name, const struct dpkg_arch *arch) +{ + struct pkgset *set; + struct pkginfo *pkg; + + set = pkg_hash_find_set(name); + pkg = pkg_hash_get_pkg(set, arch); + + return pkg; +} + +/** + * Return the number of package sets available in the database. + * + * @return The number of package sets. + */ +int +pkg_hash_count_set(void) +{ + return nset; +} + +/** + * Return the number of package instances available in the database. + * + * @return The number of package instances. + */ +int +pkg_hash_count_pkg(void) +{ + return npkg; +} + +struct pkg_hash_iter { + struct pkginfo *pkg; + int nbinn; +}; + +/** + * Create a new package iterator. + * + * It can iterate either over package sets or over package instances. + * + * @return The iterator. + */ +struct pkg_hash_iter * +pkg_hash_iter_new(void) +{ + struct pkg_hash_iter *iter; + + iter = m_malloc(sizeof(*iter)); + iter->pkg = NULL; + iter->nbinn = 0; + + return iter; +} + +/** + * Return the next package set in the database. + * + * If no further package set is available, it will return NULL. + * + * @name iter The iterator. + * + * @return A package set. + */ +struct pkgset * +pkg_hash_iter_next_set(struct pkg_hash_iter *iter) +{ + struct pkgset *set; + + while (!iter->pkg) { + if (iter->nbinn >= BINS) + return NULL; + if (bins[iter->nbinn]) + iter->pkg = &bins[iter->nbinn]->pkg; + iter->nbinn++; + } + + set = iter->pkg->set; + if (set->next) + iter->pkg = &set->next->pkg; + else + iter->pkg = NULL; + + return set; +} + +/** + * Return the next package instance in the database. + * + * If no further package instance is available, it will return NULL. Note + * that it will return all instances of a given package set in sequential + * order. The first instance for a given package set will always correspond + * to the native architecture even if that package is not installed or + * available. + * + * @name iter The iterator. + * + * @return A package instance. + */ +struct pkginfo * +pkg_hash_iter_next_pkg(struct pkg_hash_iter *iter) +{ + struct pkginfo *pkg; + + while (!iter->pkg) { + if (iter->nbinn >= BINS) + return NULL; + if (bins[iter->nbinn]) + iter->pkg = &bins[iter->nbinn]->pkg; + iter->nbinn++; + } + + pkg = iter->pkg; + if (pkg->arch_next) + iter->pkg = pkg->arch_next; + else if (pkg->set->next) + iter->pkg = &pkg->set->next->pkg; + else + iter->pkg = NULL; + + return pkg; +} + +/** + * Free the package database iterator. + * + * @name iter The iterator. + */ +void +pkg_hash_iter_free(struct pkg_hash_iter *iter) +{ + free(iter); +} + +void +pkg_hash_reset(void) +{ + dpkg_arch_reset_list(); + nffreeall(); + nset = 0; + npkg = 0; + memset(bins, 0, sizeof(bins)); +} + +void +pkg_hash_report(FILE *file) +{ + int i, c; + struct pkgset *pkg; + int *freq; + int empty = 0, used = 0, collided = 0; + + freq = m_malloc(sizeof(int) * nset + 1); + for (i = 0; i <= nset; i++) + freq[i] = 0; + for (i=0; i<BINS; i++) { + for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next); + fprintf(file, "pkg-hash: bin %5d has %7d\n", i, c); + if (c == 0) + empty++; + else if (c == 1) + used++; + else { + used++; + collided++; + } + freq[c]++; + } + for (i = nset; i > 0 && freq[i] == 0; i--); + while (i >= 0) { + fprintf(file, "pkg-hash: size %7d occurs %5d times\n", i, freq[i]); + i--; + } + fprintf(file, "pkg-hash: bins empty %d\n", empty); + fprintf(file, "pkg-hash: bins used %d (collided %d)\n", used, collided); + + m_output(file, "<hash report>"); + + free(freq); +} |