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 : return *pointerp;
93 : 0 : pointerp = &(*pointerp)->next;
94 : : }
95 : :
96 [ + + ]: 250 : if (flags & FHFF_NO_NEW)
97 : 8 : return NULL;
98 : :
99 : 242 : newnode = nfmalloc(sizeof(*newnode));
100 : 242 : memset(newnode, 0, sizeof(*newnode));
101 [ + + + - : 242 : if ((flags & FHFF_NO_COPY) && name > orig_name && name[-1] == '/') {
+ - ]
102 : 1 : newnode->name = name - 1;
103 : : } else {
104 : 241 : char *newname = nfmalloc(strlen(name) + 2);
105 : :
106 : 241 : newname[0] = '/';
107 : 241 : strcpy(newname + 1, name);
108 : 241 : newnode->name = newname;
109 : : }
110 : 242 : *pointerp = newnode;
111 : 242 : nfiles++;
112 : :
113 : 242 : return newnode;
114 : : }
115 : :
116 : : void
117 : 0 : fsys_hash_report(FILE *file)
118 : : {
119 : : struct fsys_namenode *node;
120 : : int i, c;
121 : : int *freq;
122 : 0 : int empty = 0, used = 0, collided = 0;
123 : :
124 : 0 : freq = m_malloc(sizeof(freq[0]) * nfiles + 1);
125 [ # # ]: 0 : for (i = 0; i <= nfiles; i++)
126 : 0 : freq[i] = 0;
127 [ # # ]: 0 : for (i = 0; i < BINS; i++) {
128 [ # # ]: 0 : for (c = 0, node = bins[i]; node; c++, node = node->next);
129 : 0 : fprintf(file, "fsys-hash: bin %5d has %7d\n", i, c);
130 [ # # ]: 0 : if (c == 0)
131 : 0 : empty++;
132 [ # # ]: 0 : else if (c == 1)
133 : 0 : used++;
134 : : else {
135 : 0 : used++;
136 : 0 : collided++;
137 : : }
138 : 0 : freq[c]++;
139 : : }
140 [ # # # # ]: 0 : for (i = nfiles; i > 0 && freq[i] == 0; i--);
141 [ # # ]: 0 : while (i >= 0) {
142 : 0 : fprintf(file, "fsys-hash: size %7d occurs %5d times\n",
143 : 0 : i, freq[i]);
144 : 0 : i--;
145 : : }
146 : 0 : fprintf(file, "fsys-hash: bins empty %d\n", empty);
147 : 0 : fprintf(file, "fsys-hash: bins used %d (collided %d)\n", used,
148 : : collided);
149 : :
150 : 0 : m_output(file, "<hash report>");
151 : :
152 : 0 : free(freq);
153 : 0 : }
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 : 43 : fsys_hash_iter_new(void)
166 : : {
167 : : struct fsys_hash_iter *iter;
168 : :
169 : 43 : iter = m_malloc(sizeof(*iter));
170 : 43 : iter->namenode = NULL;
171 : 43 : iter->nbinn = 0;
172 : :
173 : 43 : return iter;
174 : : }
175 : :
176 : : struct fsys_namenode *
177 : 200 : fsys_hash_iter_next(struct fsys_hash_iter *iter)
178 : : {
179 : 200 : struct fsys_namenode *fnn = NULL;
180 : :
181 [ + + ]: 11272177 : while (!iter->namenode) {
182 [ + + ]: 11272020 : if (iter->nbinn >= BINS)
183 : 43 : return NULL;
184 : 11271977 : iter->namenode = bins[iter->nbinn++];
185 : : }
186 : 157 : fnn = iter->namenode;
187 : 157 : iter->namenode = fnn->next;
188 : :
189 : 157 : return fnn;
190 : : }
191 : :
192 : : void
193 : 43 : fsys_hash_iter_free(struct fsys_hash_iter *iter)
194 : : {
195 : 43 : free(iter);
196 : 43 : }
|
