Branch data Line data Source code
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 : 2 : fsys_hash_init(void) 45 : : { 46 : : struct fsys_namenode *fnn; 47 : : int i; 48 : : 49 [ + + ]: 524280 : for (i = 0; i < BINS; i++) { 50 [ + + ]: 524281 : for (fnn = bins[i]; fnn; fnn = fnn->next) { 51 : 3 : fnn->flags = 0; 52 : 3 : fnn->oldhash = NULL; 53 : 3 : fnn->newhash = NULL; 54 : 3 : fnn->file_ondisk_id = NULL; 55 : : } 56 : : } 57 : 2 : } 58 : : 59 : : void 60 : 1 : fsys_hash_reset(void) 61 : : { 62 : 1 : memset(bins, 0, sizeof(bins)); 63 : 1 : nfiles = 0; 64 : 1 : } 65 : : 66 : : int 67 : 9 : fsys_hash_entries(void) 68 : : { 69 : 9 : return nfiles; 70 : : } 71 : : 72 : : struct fsys_namenode * 73 : 280 : fsys_hash_find_node(const char *name, enum fsys_hash_find_flags flags) 74 : : { 75 : : struct fsys_namenode **pointerp, *newnode; 76 : 280 : const char *orig_name = name; 77 : : 78 : : /* We skip initial slashes and ‘./’ pairs, and add our own single 79 : : * leading slash. */ 80 : 280 : name = path_skip_slash_dotslash(name); 81 : : 82 : 280 : pointerp = bins + (str_fnv_hash(name) % (BINS)); 83 [ + + ]: 280 : 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 [ - + ]: 30 : if ((*pointerp)->name[0] != '/') 88 : 0 : internerr("filename node '%s' does not start with '/'", 89 : : (*pointerp)->name); 90 : : 91 [ + - ]: 30 : if (strcmp((*pointerp)->name + 1, name) == 0) 92 : 30 : break; 93 : 0 : pointerp = &(*pointerp)->next; 94 : : } 95 [ + + ]: 280 : if (*pointerp) 96 : 30 : return *pointerp; 97 : : 98 [ + + ]: 250 : if (flags & FHFF_NONE) 99 : 8 : return NULL; 100 : : 101 : 242 : newnode = nfmalloc(sizeof(*newnode)); 102 : 242 : memset(newnode, 0, sizeof(*newnode)); 103 [ + + + - : 242 : if ((flags & FHFF_NOCOPY) && name > orig_name && name[-1] == '/') { + - ] 104 : 1 : newnode->name = name - 1; 105 : : } else { 106 : 241 : char *newname = nfmalloc(strlen(name) + 2); 107 : : 108 : 241 : newname[0] = '/'; 109 : 241 : strcpy(newname + 1, name); 110 : 241 : newnode->name = newname; 111 : : } 112 : 242 : *pointerp = newnode; 113 : 242 : nfiles++; 114 : : 115 : 242 : return newnode; 116 : : } 117 : : 118 : : void 119 : 0 : fsys_hash_report(FILE *file) 120 : : { 121 : : struct fsys_namenode *node; 122 : : int i, c; 123 : : int *freq; 124 : 0 : int empty = 0, used = 0, collided = 0; 125 : : 126 : 0 : freq = m_malloc(sizeof(freq[0]) * nfiles + 1); 127 [ # # ]: 0 : for (i = 0; i <= nfiles; i++) 128 : 0 : freq[i] = 0; 129 [ # # ]: 0 : for (i = 0; i < BINS; i++) { 130 [ # # ]: 0 : for (c = 0, node = bins[i]; node; c++, node = node->next); 131 : 0 : fprintf(file, "fsys-hash: bin %5d has %7d\n", i, c); 132 [ # # ]: 0 : if (c == 0) 133 : 0 : empty++; 134 [ # # ]: 0 : else if (c == 1) 135 : 0 : used++; 136 : : else { 137 : 0 : used++; 138 : 0 : collided++; 139 : : } 140 : 0 : freq[c]++; 141 : : } 142 [ # # # # ]: 0 : for (i = nfiles; i > 0 && freq[i] == 0; i--); 143 [ # # ]: 0 : while (i >= 0) { 144 : 0 : fprintf(file, "fsys-hash: size %7d occurs %5d times\n", 145 : 0 : i, freq[i]); 146 : 0 : i--; 147 : : } 148 : 0 : fprintf(file, "fsys-hash: bins empty %d\n", empty); 149 : 0 : fprintf(file, "fsys-hash: bins used %d (collided %d)\n", used, 150 : : collided); 151 : : 152 : 0 : m_output(file, "<hash report>"); 153 : : 154 : 0 : free(freq); 155 : 0 : } 156 : : 157 : : /* 158 : : * Forward iterator. 159 : : */ 160 : : 161 : : struct fsys_hash_iter { 162 : : struct fsys_namenode *namenode; 163 : : int nbinn; 164 : : }; 165 : : 166 : : struct fsys_hash_iter * 167 : 43 : fsys_hash_iter_new(void) 168 : : { 169 : : struct fsys_hash_iter *iter; 170 : : 171 : 43 : iter = m_malloc(sizeof(*iter)); 172 : 43 : iter->namenode = NULL; 173 : 43 : iter->nbinn = 0; 174 : : 175 : 43 : return iter; 176 : : } 177 : : 178 : : struct fsys_namenode * 179 : 200 : fsys_hash_iter_next(struct fsys_hash_iter *iter) 180 : : { 181 : 200 : struct fsys_namenode *fnn = NULL; 182 : : 183 [ + + ]: 11272177 : while (!iter->namenode) { 184 [ + + ]: 11272020 : if (iter->nbinn >= BINS) 185 : 43 : return NULL; 186 : 11271977 : iter->namenode = bins[iter->nbinn++]; 187 : : } 188 : 157 : fnn = iter->namenode; 189 : 157 : iter->namenode = fnn->next; 190 : : 191 : 157 : return fnn; 192 : : } 193 : : 194 : : void 195 : 43 : fsys_hash_iter_free(struct fsys_hash_iter *iter) 196 : : { 197 : 43 : free(iter); 198 : 43 : }