2
* libdpkg - Debian packaging suite library routines
3
* dpkg-db.h - Low level package database routines (hash tables, etc.)
5
* Copyright © 1995 Ian Jackson <ian@chiark.greenend.org.uk>
6
* Copyright © 2011 Linaro Limited
7
* Copyright © 2011 Raphaël Hertzog <hertzog@debian.org>
9
* This is free software; you can redistribute it and/or modify
10
* it under the terms of the GNU General Public License as published by
11
* the Free Software Foundation; either version 2 of the License, or
12
* (at your option) any later version.
14
* This is distributed in the hope that it will be useful,
15
* but WITHOUT ANY WARRANTY; without even the implied warranty of
16
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17
* GNU General Public License for more details.
19
* You should have received a copy of the GNU General Public License
20
* along with this program. If not, see <http://www.gnu.org/licenses/>.
31
#include <dpkg/i18n.h>
32
#include <dpkg/dpkg.h>
33
#include <dpkg/dpkg-db.h>
34
#include <dpkg/arch.h>
36
/* This must always be a prime for optimal performance.
37
* With 4093 buckets, we glean a 20% speedup, for 8191 buckets
38
* we get 23%. The nominal increase in memory usage is a mere
39
* sizeof(void *) * 8063 (i.e. less than 32 KiB on 32bit systems). */
42
static struct pkgset *bins[BINS];
43
static int npkg, nset;
45
#define FNV_offset_basis 2166136261ul
46
#define FNV_mixing_prime 16777619ul
49
* Fowler/Noll/Vo -- simple string hash.
51
* For more info, see <http://www.isthe.com/chongo/tech/comp/fnv/index.html>.
53
static unsigned int hash(const char *name) {
54
register unsigned int h = FNV_offset_basis;
55
register unsigned int p = FNV_mixing_prime;
63
void blankversion(struct versionrevision *version) {
65
version->version= version->revision= NULL;
69
pkgset_blank(struct pkgset *set)
72
set->depended.available = NULL;
73
set->depended.installed = NULL;
79
pkg_blank(struct pkginfo *pigp)
82
pigp->arch_next = NULL;
83
pigp->status= stat_notinstalled;
84
pigp->eflag = eflag_ok;
85
pigp->want= want_unknown;
86
pigp->priority= pri_unknown;
87
pigp->otherpriority = NULL;
89
blankversion(&pigp->configversion);
91
pigp->clientdata= NULL;
92
pigp->trigaw.head = pigp->trigaw.tail = NULL;
93
pigp->othertrigaw_head = NULL;
94
pigp->trigpend_head = NULL;
95
pkgbin_blank(&pigp->installed, false);
96
pkgbin_blank(&pigp->available, false);
100
pkgbin_blank(struct pkgbin *pifp, bool keep_arch)
102
pifp->essential = false;
103
pifp->multiarch = multiarch_no;
105
pifp->description= pifp->maintainer= pifp->source= pifp->installedsize= pifp->bugs= pifp->origin= NULL;
107
pifp->arch = dpkg_arch_find(NULL);
108
blankversion(&pifp->version);
109
pifp->conffiles= NULL;
113
static int nes(const char *s) { return s && *s; }
116
* Check if a pkg is informative.
118
* Used by dselect and dpkg query options as an aid to decide whether to
119
* display things, and by dump to decide whether to write them out.
122
pkg_is_informative(struct pkginfo *pkg, struct pkgbin *info)
124
if (info == &pkg->installed &&
125
(pkg->want != want_unknown ||
126
pkg->eflag != eflag_ok ||
127
pkg->status != stat_notinstalled ||
128
informativeversion(&pkg->configversion)))
129
/* We ignore Section and Priority, as these tend to hang around. */
132
nes(info->description) ||
133
nes(info->maintainer) ||
136
nes(info->installedsize) ||
138
informativeversion(&info->version) ||
146
* Return the package set with the given name.
148
* If the package already exists in the internal database, then it returns
149
* the existing structure. Otherwise it allocates a new one and will
150
* return it. The actual name associated to the package set is a lowercase
151
* version of the name given in parameter.
153
* A package set (struct pkgset) can be composed of multiple package
154
* instances (struct pkginfo) where each instance is distinguished
155
* by its architecture (as recorded in pkg.{installed,available}.architecture).
157
* @param inname Name of the package set.
158
* @return The package set.
161
pkg_db_find_set(const char *inname)
163
struct pkgset **pointerp, *newpkg;
164
char *name = m_strdup(inname), *p;
167
while(*p) { *p= tolower(*p); p++; }
169
pointerp= bins + (hash(name) % (BINS));
170
while (*pointerp && strcasecmp((*pointerp)->name,name))
171
pointerp= &(*pointerp)->next;
177
newpkg = nfmalloc(sizeof(struct pkgset));
178
pkgset_blank(newpkg);
179
newpkg->name= nfstrsave(name);
190
* Return the package instance with the given name and architecture.
192
* It first uses pkg_db_find_set() to retrieve the right package set and
193
* then traverse the various instances to find out whether there's one
194
* matching the given architecture. If yes, it returns it. Otherwise it
195
* allocates an new instance and register it in the package set berfore
198
* If the requested architecture is a NULL pointer, it will be dealt like
199
* the native architecture and the special architecture "all": it will
200
* always return the first instance in the list (this one always exists
201
* since it's part of the pksget structure).
203
* @param name The package name.
204
* @param arch The requested architecture.
205
* @return The package instance.
208
pkg_db_find_pkg(const char *name, const struct dpkg_arch *arch)
211
struct pkginfo *pkg, **pkgp;
213
set = pkg_db_find_set(name);
215
if (!arch || arch->type == arch_native || arch->type == arch_all ||
216
arch->type == arch_none) {
217
/* Must always use the first instance */
218
assert(pkg->installed.arch->type == arch_native ||
219
pkg->installed.arch->type == arch_all ||
220
pkg->installed.arch->type == arch_none);
224
/* Look into alternate instances for the wanted architecture */
225
pkgp = &pkg->arch_next;
227
if (!(*pkgp)->installed.arch) {
228
/* pkginfo is not differentiated, use it */
229
(*pkgp)->installed.arch = arch;
230
(*pkgp)->available.arch = arch;
233
if ((*pkgp)->installed.arch == arch)
235
pkgp = &(*pkgp)->arch_next;
238
/* Need to create a new instance for the wanted architecture */
239
pkg = nfmalloc(sizeof(struct pkginfo));
242
pkg->installed.arch = arch;
243
pkg->available.arch = arch;
251
* Return the number of package sets available in the database.
253
* @return The number of package sets.
256
pkg_db_count_set(void)
262
* Return the number of package instances available in the database.
264
* @return The number of package instances.
267
pkg_db_count_pkg(void)
273
struct pkginfo *pigp;
278
* Create a new package iterator.
280
* It can iterate either over package sets or over package instances.
282
* @return The iterator.
285
pkg_db_iter_new(void)
287
struct pkgiterator *i;
288
i= m_malloc(sizeof(struct pkgiterator));
295
* Return the next package set in the database.
297
* If no further package set is available, it will return NULL.
299
* @name it The iterator.
300
* @return A package set.
303
pkg_db_iter_next_set(struct pkgiterator *it)
308
if (it->nbinn >= BINS)
311
it->pigp = &bins[it->nbinn]->pkg;
317
it->pigp = &set->next->pkg;
325
* Return the next package instance in the database.
327
* If no further package instance is available, it will return NULL. Note
328
* that it will return all instances of a given package set in sequential
329
* order. The first instance for a given package set will always
330
* correspond to the native architecture even if that package is not
331
* installed or available.
333
* @name i The iterator.
334
* @return A package instance.
337
pkg_db_iter_next_pkg(struct pkgiterator *i)
342
if (i->nbinn >= BINS) return NULL;
344
i->pigp = &bins[i->nbinn]->pkg;
350
i->pigp = r->arch_next;
351
else if (r->set->next)
352
i->pigp = &r->set->next->pkg;
360
* Free up the resources associated to the package iterator.
362
* @name i The iterator.
365
pkg_db_iter_free(struct pkgiterator *i)
377
for (i=0; i<BINS; i++) bins[i]= NULL;
381
void hashreport(FILE *file) {
386
freq = m_malloc(sizeof(int) * nset + 1);
387
for (i = 0; i <= nset; i++) freq[i]= 0;
388
for (i=0; i<BINS; i++) {
389
for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next);
390
fprintf(file,"bin %5d has %7d\n",i,c);
393
for (i = nset; i > 0 && freq[i] == 0; i--);
395
fprintf(file, "size %7d occurs %5d times\n", i, freq[i]);
399
m_output(file, "<hash report>");