Branch data Line data Source code
1 : : /*
2 : : * libdpkg - Debian packaging suite library routines
3 : : * pkg-hash.c - low level package database routines (hash tables, etc.)
4 : : *
5 : : * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk>
6 : : * Copyright © 2008-2014 Guillem Jover <guillem@debian.org>
7 : : * Copyright © 2011 Linaro Limited
8 : : * Copyright © 2011 Raphaël Hertzog <hertzog@debian.org>
9 : : *
10 : : * This is free software; you can redistribute it and/or modify
11 : : * it under the terms of the GNU General Public License as published by
12 : : * the Free Software Foundation; either version 2 of the License, or
13 : : * (at your option) any later version.
14 : : *
15 : : * This is distributed in the hope that it will be useful,
16 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 : : * GNU General Public License for more details.
19 : : *
20 : : * You should have received a copy of the GNU General Public License
21 : : * along with this program. If not, see <https://www.gnu.org/licenses/>.
22 : : */
23 : :
24 : : #include <config.h>
25 : : #include <compat.h>
26 : :
27 : : #include <string.h>
28 : : #include <stdlib.h>
29 : :
30 : : #include <dpkg/i18n.h>
31 : : #include <dpkg/c-ctype.h>
32 : : #include <dpkg/dpkg.h>
33 : : #include <dpkg/dpkg-db.h>
34 : : #include <dpkg/string.h>
35 : : #include <dpkg/arch.h>
36 : :
37 : : /*
38 : : * This must always be a prime for optimal performance.
39 : : *
40 : : * We use a number that is close to the amount of packages currently present
41 : : * in a Debian suite, so that installed and available packages do not add
42 : : * tons of collisions.
43 : : *
44 : : * The memory usage is «BINS * sizeof(void *)».
45 : : */
46 : : #define BINS 65521
47 : :
48 : : static struct pkgset *bins[BINS];
49 : : static int npkg, nset;
50 : :
51 : : /**
52 : : * Return the package set with the given name.
53 : : *
54 : : * If the package already exists in the internal database, then it returns
55 : : * the existing structure. Otherwise it allocates a new one and will return
56 : : * it. The actual name associated to the package set is a lowercase version
57 : : * of the name given in parameter.
58 : : *
59 : : * A package set (struct pkgset) can be composed of multiple package instances
60 : : * (struct pkginfo) where each instance is distinguished by its architecture
61 : : * (as recorded in pkg.installed.arch and pkg.available.arch).
62 : : *
63 : : * @param inname Name of the package set.
64 : : *
65 : : * @return The package set.
66 : : */
67 : : struct pkgset *
68 : 129 : pkg_hash_find_set(const char *inname)
69 : : {
70 : : struct pkgset **setp, *new_set;
71 : 129 : char *name = m_strdup(inname), *p;
72 : :
73 : 129 : p= name;
74 [ + + ]: 1704 : while (*p) {
75 : 1575 : *p = c_tolower(*p);
76 : 1575 : p++;
77 : : }
78 : :
79 : 129 : setp = bins + (str_fnv_hash(name) % (BINS));
80 [ + + - + ]: 129 : while (*setp && strcasecmp((*setp)->name, name))
81 : 0 : setp = &(*setp)->next;
82 [ + + ]: 129 : if (*setp) {
83 : 54 : free(name);
84 : 54 : return *setp;
85 : : }
86 : :
87 : 75 : new_set = nfmalloc(sizeof(*new_set));
88 : 75 : pkgset_blank(new_set);
89 : 75 : new_set->name = nfstrsave(name);
90 : 75 : new_set->next = NULL;
91 : 75 : *setp = new_set;
92 : 75 : nset++;
93 : 75 : npkg++;
94 : :
95 : 75 : free(name);
96 : :
97 : 75 : return new_set;
98 : : }
99 : :
100 : : /**
101 : : * Return the singleton package instance from a package set.
102 : : *
103 : : * This means, if none are installed either an instance with native or
104 : : * all arch or the first if none found, the single installed instance,
105 : : * or NULL if more than one instance is installed.
106 : : *
107 : : * @param set The package set to use.
108 : : *
109 : : * @return The singleton package instance.
110 : : */
111 : : struct pkginfo *
112 : 3 : pkg_hash_get_singleton(struct pkgset *set)
113 : : {
114 : : struct pkginfo *pkg;
115 : :
116 [ + + + ]: 3 : switch (pkgset_installed_instances(set)) {
117 : 1 : case 0:
118 : : /* Pick an available candidate. */
119 [ + + ]: 2 : for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
120 : 1 : const struct dpkg_arch *arch = pkg->available.arch;
121 : :
122 [ + - - + ]: 1 : if (arch->type == DPKG_ARCH_NATIVE || arch->type == DPKG_ARCH_ALL)
123 : 0 : return pkg;
124 : : }
125 : : /* Or failing that, the first entry. */
126 : 1 : return &set->pkg;
127 : 1 : case 1:
128 [ + - ]: 1 : for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
129 [ + - ]: 1 : if (pkg->status > PKG_STAT_NOTINSTALLED)
130 : 1 : return pkg;
131 : : }
132 : 0 : internerr("pkgset '%s' should have one installed instance", set->name);
133 : 1 : default:
134 : 1 : return NULL;
135 : : }
136 : : }
137 : :
138 : : /**
139 : : * Return the singleton package instance with the given name.
140 : : *
141 : : * @param name The package name.
142 : : *
143 : : * @return The package instance.
144 : : */
145 : : struct pkginfo *
146 : 2 : pkg_hash_find_singleton(const char *name)
147 : : {
148 : : struct pkgset *set;
149 : : struct pkginfo *pkg;
150 : :
151 : 2 : set = pkg_hash_find_set(name);
152 : 2 : pkg = pkg_hash_get_singleton(set);
153 [ - + ]: 2 : if (pkg == NULL)
154 : 0 : ohshit(_("ambiguous package name '%s' with more "
155 : : "than one installed instance"), set->name);
156 : :
157 : 2 : return pkg;
158 : : }
159 : :
160 : : /**
161 : : * Return the package instance in a set with the given architecture.
162 : : *
163 : : * It traverse the various instances to find out whether there's one
164 : : * matching the given architecture. If found, it returns it. Otherwise it
165 : : * allocates a new instance and registers it in the package set before
166 : : * returning it.
167 : : *
168 : : * @param set The package set to use.
169 : : * @param arch The requested architecture.
170 : : *
171 : : * @return The package instance.
172 : : */
173 : : struct pkginfo *
174 : 37 : pkg_hash_get_pkg(struct pkgset *set, const struct dpkg_arch *arch)
175 : : {
176 : : struct pkginfo *pkg, **pkgp;
177 : :
178 [ - + ]: 37 : if (arch == NULL)
179 : 0 : internerr("arch argument is NULL");
180 [ - + ]: 37 : if (arch->type == DPKG_ARCH_NONE)
181 : 0 : internerr("arch argument is none");
182 : :
183 : 37 : pkg = &set->pkg;
184 : :
185 : : /* If there's a single unused slot, let's use that. */
186 [ + + + - ]: 37 : if (pkg->installed.arch->type == DPKG_ARCH_NONE && pkg->arch_next == NULL) {
187 : : /* We can only initialize the arch pkgbin members, because those are used
188 : : * to find instances, anything else will be overwritten at parse time. */
189 : 34 : pkg->installed.arch = arch;
190 : 34 : pkg->available.arch = arch;
191 : 34 : return pkg;
192 : : }
193 : :
194 : : /* Match the slot with the most appropriate architecture. The installed
195 : : * architecture always has preference over the available one, as there's
196 : : * a small time window on cross-grades, where they might differ. */
197 : : /* cppcheck-suppress[knownConditionTrueFalse,knownPointerToBool]:
198 : : * False positive, the condition always ends up being false. */
199 [ + + ]: 6 : for (pkgp = &pkg; *pkgp; pkgp = &(*pkgp)->arch_next) {
200 [ + + ]: 4 : if ((*pkgp)->installed.arch == arch)
201 : 1 : return *pkgp;
202 : : }
203 : :
204 : : /* Need to create a new instance for the wanted architecture. */
205 : 2 : pkg = nfmalloc(sizeof(*pkg));
206 : 2 : pkg_blank(pkg);
207 : 2 : pkg->set = set;
208 : 2 : pkg->arch_next = NULL;
209 : : /* We can only initialize the arch pkgbin members, because those are used
210 : : * to find instances, anything else will be overwritten at parse time. */
211 : 2 : pkg->installed.arch = arch;
212 : 2 : pkg->available.arch = arch;
213 : 2 : *pkgp = pkg;
214 : 2 : npkg++;
215 : :
216 : 2 : return pkg;
217 : : }
218 : :
219 : : /**
220 : : * Return the package instance with the given name and architecture.
221 : : *
222 : : * @param name The package name.
223 : : * @param arch The requested architecture.
224 : : *
225 : : * @return The package instance.
226 : : */
227 : : struct pkginfo *
228 : 5 : pkg_hash_find_pkg(const char *name, const struct dpkg_arch *arch)
229 : : {
230 : : struct pkgset *set;
231 : : struct pkginfo *pkg;
232 : :
233 : 5 : set = pkg_hash_find_set(name);
234 : 5 : pkg = pkg_hash_get_pkg(set, arch);
235 : :
236 : 5 : return pkg;
237 : : }
238 : :
239 : : /**
240 : : * Return the number of package sets available in the database.
241 : : *
242 : : * @return The number of package sets.
243 : : */
244 : : int
245 : 14 : pkg_hash_count_set(void)
246 : : {
247 : 14 : return nset;
248 : : }
249 : :
250 : : /**
251 : : * Return the number of package instances available in the database.
252 : : *
253 : : * @return The number of package instances.
254 : : */
255 : : int
256 : 14 : pkg_hash_count_pkg(void)
257 : : {
258 : 14 : return npkg;
259 : : }
260 : :
261 : : struct pkg_hash_iter {
262 : : struct pkginfo *pkg;
263 : : int nbinn;
264 : : };
265 : :
266 : : /**
267 : : * Create a new package iterator.
268 : : *
269 : : * It can iterate either over package sets or over package instances.
270 : : *
271 : : * @return The iterator.
272 : : */
273 : : struct pkg_hash_iter *
274 : 8 : pkg_hash_iter_new(void)
275 : : {
276 : : struct pkg_hash_iter *iter;
277 : :
278 : 8 : iter = m_malloc(sizeof(*iter));
279 : 8 : iter->pkg = NULL;
280 : 8 : iter->nbinn = 0;
281 : :
282 : 8 : return iter;
283 : : }
284 : :
285 : : /**
286 : : * Return the next package set in the database.
287 : : *
288 : : * If no further package set is available, it will return NULL.
289 : : *
290 : : * @name iter The iterator.
291 : : *
292 : : * @return A package set.
293 : : */
294 : : struct pkgset *
295 : 4 : pkg_hash_iter_next_set(struct pkg_hash_iter *iter)
296 : : {
297 : : struct pkgset *set;
298 : :
299 [ + + ]: 65525 : while (!iter->pkg) {
300 [ + + ]: 65522 : if (iter->nbinn >= BINS)
301 : 1 : return NULL;
302 [ + + ]: 65521 : if (bins[iter->nbinn])
303 : 3 : iter->pkg = &bins[iter->nbinn]->pkg;
304 : 65521 : iter->nbinn++;
305 : : }
306 : :
307 : 3 : set = iter->pkg->set;
308 [ - + ]: 3 : if (set->next)
309 : 0 : iter->pkg = &set->next->pkg;
310 : : else
311 : 3 : iter->pkg = NULL;
312 : :
313 : 3 : return set;
314 : : }
315 : :
316 : : /**
317 : : * Return the next package instance in the database.
318 : : *
319 : : * If no further package instance is available, it will return NULL. Note
320 : : * that it will return all instances of a given package set in sequential
321 : : * order. The first instance for a given package set will always correspond
322 : : * to the native architecture even if that package is not installed or
323 : : * available.
324 : : *
325 : : * @name iter The iterator.
326 : : *
327 : : * @return A package instance.
328 : : */
329 : : struct pkginfo *
330 : 12 : pkg_hash_iter_next_pkg(struct pkg_hash_iter *iter)
331 : : {
332 : : struct pkginfo *pkg;
333 : :
334 [ + + ]: 458659 : while (!iter->pkg) {
335 [ + + ]: 458654 : if (iter->nbinn >= BINS)
336 : 7 : return NULL;
337 [ + + ]: 458647 : if (bins[iter->nbinn])
338 : 3 : iter->pkg = &bins[iter->nbinn]->pkg;
339 : 458647 : iter->nbinn++;
340 : : }
341 : :
342 : 5 : pkg = iter->pkg;
343 [ + + ]: 5 : if (pkg->arch_next)
344 : 2 : iter->pkg = pkg->arch_next;
345 [ - + ]: 3 : else if (pkg->set->next)
346 : 0 : iter->pkg = &pkg->set->next->pkg;
347 : : else
348 : 3 : iter->pkg = NULL;
349 : :
350 : 5 : return pkg;
351 : : }
352 : :
353 : : /**
354 : : * Free the package database iterator.
355 : : *
356 : : * @name iter The iterator.
357 : : */
358 : : void
359 : 8 : pkg_hash_iter_free(struct pkg_hash_iter *iter)
360 : : {
361 : 8 : free(iter);
362 : 8 : }
363 : :
364 : : void
365 : 53 : pkg_hash_reset(void)
366 : : {
367 : 53 : dpkg_arch_reset_list();
368 : 53 : nffreeall();
369 : 53 : nset = 0;
370 : 53 : npkg = 0;
371 : 53 : memset(bins, 0, sizeof(bins));
372 : 53 : }
373 : :
374 : : void
375 : 0 : pkg_hash_report(FILE *file)
376 : : {
377 : : int i, c;
378 : : struct pkgset *pkg;
379 : : int *freq;
380 : 0 : int empty = 0, used = 0, collided = 0;
381 : :
382 : 0 : freq = m_malloc(sizeof(int) * nset + 1);
383 [ # # ]: 0 : for (i = 0; i <= nset; i++)
384 : 0 : freq[i] = 0;
385 [ # # ]: 0 : for (i=0; i<BINS; i++) {
386 [ # # ]: 0 : for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next);
387 : 0 : fprintf(file, "pkg-hash: bin %5d has %7d\n", i, c);
388 [ # # ]: 0 : if (c == 0)
389 : 0 : empty++;
390 [ # # ]: 0 : else if (c == 1)
391 : 0 : used++;
392 : : else {
393 : 0 : used++;
394 : 0 : collided++;
395 : : }
396 : 0 : freq[c]++;
397 : : }
398 [ # # # # ]: 0 : for (i = nset; i > 0 && freq[i] == 0; i--);
399 [ # # ]: 0 : while (i >= 0) {
400 : 0 : fprintf(file, "pkg-hash: size %7d occurs %5d times\n", i, freq[i]);
401 : 0 : i--;
402 : : }
403 : 0 : fprintf(file, "pkg-hash: bins empty %d\n", empty);
404 : 0 : fprintf(file, "pkg-hash: bins used %d (collided %d)\n", used, collided);
405 : :
406 : 0 : m_output(file, "<hash report>");
407 : :
408 : 0 : free(freq);
409 : 0 : }
|
