summaryrefslogtreecommitdiff
path: root/lib/database.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/database.c')
-rw-r--r--lib/database.c249
1 files changed, 249 insertions, 0 deletions
diff --git a/lib/database.c b/lib/database.c
new file mode 100644
index 000000000..9561a0fde
--- /dev/null
+++ b/lib/database.c
@@ -0,0 +1,249 @@
+/*
+ * libdpkg - Debian packaging suite library routines
+ * dpkg-db.h - Low level package database routines (hash tables, etc.)
+ *
+ * Copyright (C) 1995 Ian Jackson <iwj10@cus.cam.ac.uk>
+ *
+ * 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,
+ * 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 dpkg; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include <ctype.h>
+#include <string.h>
+
+#include "config.h"
+#include "dpkg.h"
+#include "dpkg-db.h"
+
+#define BINS (1 << 7)
+ /* This must always be a power of two. If you change it
+ * consider changing the per-character hashing factor (currently 5) too.
+ */
+
+static struct pkginfo *bins[BINS];
+static int npackages;
+
+static int hash(const char *name) {
+ int v= 0;
+ while (*name) { v *= 5; v += tolower(*name); name++; }
+ return v;
+/* These results were achieved with 128 bins, and the list of packages
+ * shown at the bottom of this file.
+ */
+/* while (*name) { v *= 17; v += tolower(*name); name++; }
+ * size 5 occurs 1 times
+ * size 4 occurs 0 times
+ * size 3 occurs 7 times
+ * size 2 occurs 32 times
+ * size 1 occurs 51 times
+ * size 0 occurs 37 times
+ */
+/* while (*name) { v *= 5; v += tolower(*name); name++; }
+ * size 4 occurs 1 times
+ * size 3 occurs 14 times
+ * size 2 occurs 20 times
+ * size 1 occurs 55 times
+ * size 0 occurs 38 times
+ */
+/* while (*name) { v *= 11; v += tolower(*name); name++; }
+ * size 5 occurs 1 times
+ * size 4 occurs 4 times
+ * size 3 occurs 9 times
+ * size 2 occurs 25 times
+ * size 1 occurs 43 times
+ * size 0 occurs 46 times
+ */
+/* while (*name) { v *= 31; v += tolower(*name); name++; }
+ * size 6 occurs 1 times
+ * size 5 occurs 0 times
+ * size 4 occurs 1 times
+ * size 3 occurs 11 times
+ * size 2 occurs 27 times
+ * size 1 occurs 44 times
+ * size 0 occurs 44 times
+ */
+/* while (*name) { v *= 111; v += tolower(*name); name++; }
+ * size 5 occurs 1 times
+ * size 4 occurs 1 times
+ * size 3 occurs 14 times
+ * size 2 occurs 23 times
+ * size 1 occurs 44 times
+ * size 0 occurs 45 times
+ */
+/* while (*name) { v += (v<<3); v += tolower(*name); name++; }
+ * size 4 occurs 5 times
+ * size 3 occurs 12 times
+ * size 2 occurs 22 times
+ * size 1 occurs 41 times
+ * size 0 occurs 48 times
+ */
+/* while (*name) { v *= 29; v += tolower(*name); name++; }
+ * size 5 occurs 1 times
+ * size 4 occurs 2 times
+ * size 3 occurs 10 times
+ * size 2 occurs 26 times
+ * size 1 occurs 46 times
+ * size 0 occurs 43 times
+ */
+/* while (*name) { v *= 13; v += tolower(*name); name++; }
+ * size 5 occurs 1 times
+ * size 4 occurs 2 times
+ * size 3 occurs 5 times
+ * size 2 occurs 30 times
+ * size 1 occurs 53 times
+ * size 0 occurs 37 times
+ */
+}
+
+void blankpackage(struct pkginfo *pigp) {
+ pigp->name= 0;
+ pigp->status= stat_notinstalled;
+ pigp->eflag= eflagv_ok;
+ pigp->want= want_unknown;
+ pigp->priority= pri_unknown;
+ pigp->section= pigp->configversion= pigp->configrevision= 0;
+ pigp->files= 0;
+ pigp->installed.valid= 0;
+ pigp->available.valid= 0;
+ pigp->clientdata= 0;
+}
+
+void blankpackageperfile(struct pkginfoperfile *pifp) {
+ pifp->essential= 0;
+ pifp->depends= 0;
+ pifp->depended= 0;
+ pifp->description= pifp->maintainer= pifp->source= 0;
+ pifp->architecture= pifp->version= pifp->revision= 0;
+ pifp->conffiles= 0;
+ pifp->arbs= 0;
+ pifp->valid= 1;
+}
+
+static int nes(const char *s) { return s && *s; }
+
+int informativeperfile(struct pkginfoperfile *info) {
+ /* Used by dselect as an aid to decide whether to display things. */
+ if (!info->valid) return 0;
+ if (info->depends ||
+ nes(info->description) ||
+ nes(info->maintainer) ||
+ nes(info->source) ||
+ nes(info->architecture) ||
+ nes(info->version) ||
+ nes(info->revision) ||
+ info->conffiles ||
+ info->arbs) return 1;
+ return 0;
+}
+
+int informative(struct pkginfo *pkg) {
+ return ((pkg->want != want_unknown && pkg->want != want_purge) ||
+ pkg->eflag != eflagv_ok ||
+ pkg->status != stat_notinstalled ||
+ nes(pkg->section) ||
+ pkg->files ||
+ pkg->priority != pri_unknown);
+}
+
+struct pkginfo *findpackage(const char *name) {
+ struct pkginfo **pointerp, *newpkg;
+
+ pointerp= bins + (hash(name) & (BINS-1));
+ while (*pointerp && strcasecmp((*pointerp)->name,name))
+ pointerp= &(*pointerp)->next;
+ if (*pointerp) return *pointerp;
+
+ newpkg= nfmalloc(sizeof(struct pkginfo));
+ blankpackage(newpkg);
+ newpkg->name= nfstrsave(name);
+ newpkg->next= 0;
+ *pointerp= newpkg;
+ npackages++;
+
+ return newpkg;
+}
+
+int countpackages(void) {
+ return npackages;
+}
+
+struct pkgiterator {
+ struct pkginfo *pigp;
+ int nbinn;
+};
+
+struct pkgiterator *iterpkgstart(void) {
+ struct pkgiterator *i;
+ i= m_malloc(sizeof(struct pkgiterator));
+ i->pigp= 0;
+ i->nbinn= 0;
+ return i;
+}
+
+struct pkginfo *iterpkgnext(struct pkgiterator *i) {
+ struct pkginfo *r;
+ while (!i->pigp) {
+ if (i->nbinn >= BINS) return 0;
+ i->pigp= bins[i->nbinn++];
+ }
+ r= i->pigp; i->pigp= r->next; return r;
+}
+
+void iterpkgend(struct pkgiterator *i) {
+ free(i);
+}
+
+void resetpackages(void) {
+ int i;
+ nffreeall();
+ npackages= 0;
+ for (i=0; i<BINS; i++) bins[i]= 0;
+}
+
+void hashreport(FILE *file) {
+ int i, c;
+ struct pkginfo *pkg;
+ int *freq;
+
+ freq= m_malloc(sizeof(int)*npackages+1);
+ for (i=0; i<=npackages; i++) freq[i]= 0;
+ for (i=0; i<BINS; i++) {
+ for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next);
+ fprintf(file,"bin %5d has %7d\n",i,c);
+ freq[c]++;
+ }
+ for (i=npackages; i>0 && freq[i]==0; i--);
+ while (i>=0) { fprintf(file,"size %7d occurs %5d times\n",i,freq[i]); i--; }
+ if (ferror(file)) ohshite("failed write during hashreport");
+}
+
+/*
+ * Test dataset package names were:
+ *
+ * agetty bash bc bdflush biff bin86 binutil binutils bison bsdutils
+ * byacc chfn cron dc dictionaries diff dlltools dpkg e2fsprogs ed
+ * elisp19 elm emacs emacs-nox emacs-x emacs19 file fileutils find
+ * flex fsprogs gas gawk gcc gcc1 gcc2 gdb ghostview ghstview glibcdoc
+ * gnuplot grep groff gs gs_both gs_svga gs_x gsfonts gxditviw gzip
+ * hello hostname idanish ifrench igerman indent inewsinn info inn
+ * ispell kbd kern1148 language ldso less libc libgr libgrdev librl
+ * lilo linuxsrc login lout lpr m4 mailx make man manpages more mount
+ * mtools ncurses netbase netpbm netstd patch perl4 perl5 procps
+ * psutils rcs rdev sed sendmail seyon shar shellutils smail svgalib
+ * syslogd sysvinit tar tcpdump tcsh tex texidoc texinfo textutils
+ * time timezone trn unzip uuencode wenglish wu-ftpd x8514 xaxe xbase
+ * xbdm2 xcomp xcoral xdevel xfig xfnt100 xfnt75 xfntbig xfntscl
+ * xgames xherc xmach32 xmach8 xmono xnet xs3 xsvga xtexstuff xv
+ * xvga16 xxgdb zip
+ */
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-13 17:00:31 +0000