lib/dpkg/fsys-hash.c

   1 /*
   2  * libdpkg - Debian packaging suite library routines
   3  * fsys-hash.c - filesystem nodes hash table
   4  *
   5  * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk>
   6  * Copyright © 2000, 2001 Wichert Akkerman <wakkerma@debian.org>
   7  * Copyright © 2008-2014 Guillem Jover <guillem@debian.org>
   8  *
   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.
  13  *
  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.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  21  */
  22
  23 #include <config.h>
  24 #include <compat.h>
  25
  26 #include <string.h>
  27 #include <stdlib.h>
  28
  29 #include <dpkg/dpkg.h>
  30 #include <dpkg/dpkg-db.h>
  31 #include <dpkg/string.h>
  32 #include <dpkg/path.h>
  33
  34 #include "fsys.h"
  35
  36 /* This must always be a prime for optimal performance.
  37  * This is the closest one to 2^18 (262144). */
  38 #define BINS 262139
  39
  40 static struct fsys_namenode *bins[BINS];
  41 static int nfiles = 0;
  42
  43 void
  44 fsys_hash_init(void)
  45 {
  46         struct fsys_namenode *fnn;
  47         int i;
  48
  49         for (i = 0; i < BINS; i++) {
  50                 for (fnn = bins[i]; fnn; fnn = fnn->next) {
  51                         fnn->flags = 0;
  52                         fnn->oldhash = NULL;
  53                         fnn->newhash = NULL;
  54                         fnn->file_ondisk_id = NULL;
  55                 }
  56         }
  57 }
  58
  59 void
  60 fsys_hash_reset(void)
  61 {
  62         memset(bins, 0, sizeof(bins));
  63         nfiles = 0;
  64 }
  65
  66 int
  67 fsys_hash_entries(void)
  68 {
  69         return nfiles;
  70 }
  71
  72 struct fsys_namenode *
  73 fsys_hash_find_node(const char *name, enum fsys_hash_find_flags flags)
  74 {
  75         struct fsys_namenode **pointerp, *newnode;
  76         const char *orig_name = name;
  77
  78         /* We skip initial slashes and ‘./’ pairs, and add our own single
  79          * leading slash. */
  80         name = path_skip_slash_dotslash(name);
  81
  82         pointerp = bins + (str_fnv_hash(name) % (BINS));
  83         while (*pointerp) {
  84                 /* XXX: This should not be needed, but it has been a constant
  85                  * source of assertions over the years. Hopefully with the
  86                  * internerr() we will get better diagnostics. */
  87                 if ((*pointerp)->name[0] != '/')
  88                         internerr("filename node '%s' does not start with '/'",
  89                                   (*pointerp)->name);
  90
  91                 if (strcmp((*pointerp)->name + 1, name) == 0)
  92                         return *pointerp;
  93                 pointerp = &(*pointerp)->next;
  94         }
  95
  96         if (flags & FHFF_NO_NEW)
  97                 return NULL;
  98
  99         newnode = nfmalloc(sizeof(*newnode));
 100         memset(newnode, 0, sizeof(*newnode));
 101         if ((flags & FHFF_NO_COPY) && name > orig_name && name[-1] == '/') {
 102                 newnode->name = name - 1;
 103         } else {
 104                 char *newname = nfmalloc(strlen(name) + 2);
 105
 106                 newname[0] = '/';
 107                 strcpy(newname + 1, name);
 108                 newnode->name = newname;
 109         }
 110         *pointerp = newnode;
 111         nfiles++;
 112
 113         return newnode;
 114 }
 115
 116 void
 117 fsys_hash_report(FILE *file)
 118 {
 119         struct fsys_namenode *node;
 120         int i, c;
 121         int *freq;
 122         int empty = 0, used = 0, collided = 0;
 123
 124         freq = m_malloc(sizeof(freq[0]) * nfiles + 1);
 125         for (i = 0; i <= nfiles; i++)
 126                 freq[i] = 0;
 127         for (i = 0; i < BINS; i++) {
 128                 for (c = 0, node = bins[i]; node; c++, node = node->next);
 129                 fprintf(file, "fsys-hash: bin %5d has %7d\n", i, c);
 130                 if (c == 0)
 131                         empty++;
 132                 else if (c == 1)
 133                         used++;
 134                 else {
 135                         used++;
 136                         collided++;
 137                 }
 138                 freq[c]++;
 139         }
 140         for (i = nfiles; i > 0 && freq[i] == 0; i--);
 141         while (i >= 0) {
 142                 fprintf(file, "fsys-hash: size %7d occurs %5d times\n",
 143                         i, freq[i]);
 144                 i--;
 145         }
 146         fprintf(file, "fsys-hash: bins empty %d\n", empty);
 147         fprintf(file, "fsys-hash: bins used %d (collided %d)\n", used,
 148                 collided);
 149
 150         m_output(file, "<hash report>");
 151
 152         free(freq);
 153 }
 154
 155 /*
 156  * Forward iterator.
 157  */
 158
 159 struct fsys_hash_iter {
 160         struct fsys_namenode *namenode;
 161         int nbinn;
 162 };
 163
 164 struct fsys_hash_iter *
 165 fsys_hash_iter_new(void)
 166 {
 167         struct fsys_hash_iter *iter;
 168
 169         iter = m_malloc(sizeof(*iter));
 170         iter->namenode = NULL;
 171         iter->nbinn = 0;
 172
 173         return iter;
 174 }
 175
 176 struct fsys_namenode *
 177 fsys_hash_iter_next(struct fsys_hash_iter *iter)
 178 {
 179         struct fsys_namenode *fnn = NULL;
 180
 181         while (!iter->namenode) {
 182                 if (iter->nbinn >= BINS)
 183                         return NULL;
 184                 iter->namenode = bins[iter->nbinn++];
 185         }
 186         fnn = iter->namenode;
 187         iter->namenode = fnn->next;
 188
 189         return fnn;
 190 }
 191
 192 void
 193 fsys_hash_iter_free(struct fsys_hash_iter *iter)
 194 {
 195         free(iter);
 196 }