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>
7
* This is free software; you can redistribute it and/or modify
8
* it under the terms of the GNU General Public License as published by
9
* the Free Software Foundation; either version 2 of the License, or
10
* (at your option) any later version.
12
* This is distributed in the hope that it will be useful,
13
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
* GNU General Public License for more details.
17
* You should have received a copy of the GNU General Public License
18
* along with this program. If not, see <http://www.gnu.org/licenses/>.
28
#include <dpkg/i18n.h>
29
#include <dpkg/dpkg.h>
30
#include <dpkg/dpkg-db.h>
33
/* This must always be a prime for optimal performance.
34
* With 4093 buckets, we glean a 20% speedup, for 8191 buckets
35
* we get 23%. The nominal increase in memory usage is a mere
36
* sizeof(void*)*8063 (I.E. less than 32KB on 32bit systems)
39
static struct pkginfo *bins[BINS];
42
#define FNV_offset_basis 2166136261ul
43
#define FNV_mixing_prime 16777619ul
45
/* Fowler/Noll/Vo -- simple string hash.
46
* For more info, see http://www.isthe.com/chongo/tech/comp/fnv/index.html
49
static unsigned int hash(const char *name) {
50
register unsigned int h = FNV_offset_basis;
51
register unsigned int p = FNV_mixing_prime;
59
void blankversion(struct versionrevision *version) {
61
version->version= version->revision= NULL;
64
void blankpackage(struct pkginfo *pigp) {
66
pigp->status= stat_notinstalled;
67
pigp->eflag = eflag_ok;
68
pigp->want= want_unknown;
69
pigp->priority= pri_unknown;
70
pigp->otherpriority = NULL;
72
blankversion(&pigp->configversion);
74
pigp->clientdata= NULL;
75
pigp->trigaw.head = pigp->trigaw.tail = NULL;
76
pigp->othertrigaw_head = NULL;
77
pigp->trigpend_head = NULL;
78
blankpackageperfile(&pigp->installed);
79
blankpackageperfile(&pigp->available);
82
void blankpackageperfile(struct pkginfoperfile *pifp) {
83
pifp->essential = false;
86
pifp->description= pifp->maintainer= pifp->source= pifp->installedsize= pifp->bugs= pifp->origin= NULL;
87
pifp->architecture= NULL;
88
blankversion(&pifp->version);
89
pifp->conffiles= NULL;
93
static int nes(const char *s) { return s && *s; }
96
informative(struct pkginfo *pkg, struct pkginfoperfile *info)
98
/* Used by dselect and dpkg query options as an aid to decide
99
* whether to display things, and by dump to decide whether to write them
102
if (info == &pkg->installed &&
103
(pkg->want != want_unknown ||
104
pkg->eflag != eflag_ok ||
105
pkg->status != stat_notinstalled ||
106
informativeversion(&pkg->configversion)))
107
/* We ignore Section and Priority, as these tend to hang around. */
110
nes(info->description) ||
111
nes(info->maintainer) ||
114
nes(info->installedsize) ||
116
informativeversion(&info->version) ||
123
struct pkginfo *findpackage(const char *inname) {
124
struct pkginfo **pointerp, *newpkg;
125
char *name = m_strdup(inname), *p;
128
while(*p) { *p= tolower(*p); p++; }
130
pointerp= bins + (hash(name) % (BINS));
131
while (*pointerp && strcasecmp((*pointerp)->name,name))
132
pointerp= &(*pointerp)->next;
133
if (*pointerp) { free(name); return *pointerp; }
135
newpkg= nfmalloc(sizeof(struct pkginfo));
136
blankpackage(newpkg);
137
newpkg->name= nfstrsave(name);
146
int countpackages(void) {
151
struct pkginfo *pigp;
155
struct pkgiterator *iterpkgstart(void) {
156
struct pkgiterator *i;
157
i= m_malloc(sizeof(struct pkgiterator));
163
struct pkginfo *iterpkgnext(struct pkgiterator *i) {
166
if (i->nbinn >= BINS) return NULL;
167
i->pigp= bins[i->nbinn++];
169
r= i->pigp; i->pigp= r->next; return r;
172
void iterpkgend(struct pkgiterator *i) {
176
void resetpackages(void) {
180
for (i=0; i<BINS; i++) bins[i]= NULL;
183
void hashreport(FILE *file) {
188
freq= m_malloc(sizeof(int)*npackages+1);
189
for (i=0; i<=npackages; i++) freq[i]= 0;
190
for (i=0; i<BINS; i++) {
191
for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next);
192
fprintf(file,"bin %5d has %7d\n",i,c);
195
for (i=npackages; i>0 && freq[i]==0; i--);
196
while (i>=0) { fprintf(file,_("size %7d occurs %5d times\n"),i,freq[i]); i--; }
198
m_output(file, "<hash report>");