Commit | Line | Data |
---|---|---|
1479465f GJ |
1 | /* |
2 | * libdpkg - Debian packaging suite library routines | |
3 | * pkg-db.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 <assert.h> | |
28 | #include <string.h> | |
29 | #include <stdlib.h> | |
30 | ||
31 | #include <dpkg/i18n.h> | |
32 | #include <dpkg/c-ctype.h> | |
33 | #include <dpkg/dpkg.h> | |
34 | #include <dpkg/dpkg-db.h> | |
35 | #include <dpkg/string.h> | |
36 | #include <dpkg/arch.h> | |
37 | ||
38 | /* This must always be a prime for optimal performance. | |
39 | * With 4093 buckets, we glean a 20% speedup, for 8191 buckets | |
40 | * we get 23%. The nominal increase in memory usage is a mere | |
41 | * sizeof(void *) * 8191 (i.e. less than 32 KiB on 32bit systems). */ | |
42 | #define BINS 8191 | |
43 | ||
44 | static struct pkgset *bins[BINS]; | |
45 | static int npkg, nset; | |
46 | ||
47 | /** | |
48 | * Return the package set with the given name. | |
49 | * | |
50 | * If the package already exists in the internal database, then it returns | |
51 | * the existing structure. Otherwise it allocates a new one and will return | |
52 | * it. The actual name associated to the package set is a lowercase version | |
53 | * of the name given in parameter. | |
54 | * | |
55 | * A package set (struct pkgset) can be composed of multiple package instances | |
56 | * (struct pkginfo) where each instance is distinguished by its architecture | |
57 | * (as recorded in pkg.installed.arch and pkg.available.arch). | |
58 | * | |
59 | * @param inname Name of the package set. | |
60 | * | |
61 | * @return The package set. | |
62 | */ | |
63 | struct pkgset * | |
64 | pkg_db_find_set(const char *inname) | |
65 | { | |
66 | struct pkgset **setp, *new_set; | |
67 | char *name = m_strdup(inname), *p; | |
68 | ||
69 | p= name; | |
70 | while (*p) { | |
71 | *p = c_tolower(*p); | |
72 | p++; | |
73 | } | |
74 | ||
75 | setp = bins + (str_fnv_hash(name) % (BINS)); | |
76 | while (*setp && strcasecmp((*setp)->name, name)) | |
77 | setp = &(*setp)->next; | |
78 | if (*setp) { | |
79 | free(name); | |
80 | return *setp; | |
81 | } | |
82 | ||
83 | new_set = nfmalloc(sizeof(struct pkgset)); | |
84 | pkgset_blank(new_set); | |
85 | new_set->name = nfstrsave(name); | |
86 | new_set->next = NULL; | |
87 | *setp = new_set; | |
88 | nset++; | |
89 | npkg++; | |
90 | ||
91 | free(name); | |
92 | ||
93 | return new_set; | |
94 | } | |
95 | ||
96 | /** | |
97 | * Return the singleton package instance from a package set. | |
98 | * | |
99 | * This means, if none are installed either an instance with native or | |
100 | * all arch or the first if none found, the single installed instance, | |
101 | * or NULL if more than one instance is installed. | |
102 | * | |
103 | * @param set The package set to use. | |
104 | * | |
105 | * @return The singleton package instance. | |
106 | */ | |
107 | struct pkginfo * | |
108 | pkg_db_get_singleton(struct pkgset *set) | |
109 | { | |
110 | struct pkginfo *pkg; | |
111 | ||
112 | switch (pkgset_installed_instances(set)) { | |
113 | case 0: | |
114 | /* Pick an available candidate. */ | |
115 | for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) { | |
116 | const struct dpkg_arch *arch = pkg->available.arch; | |
117 | ||
118 | if (arch->type == DPKG_ARCH_NATIVE || arch->type == DPKG_ARCH_ALL) | |
119 | return pkg; | |
120 | } | |
121 | /* Or failing that, the first entry. */ | |
122 | return &set->pkg; | |
123 | case 1: | |
124 | for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) { | |
125 | if (pkg->status > PKG_STAT_NOTINSTALLED) | |
126 | return pkg; | |
127 | } | |
128 | internerr("pkgset '%s' should have one installed instance", set->name); | |
129 | default: | |
130 | return NULL; | |
131 | } | |
132 | } | |
133 | ||
134 | /** | |
135 | * Return the singleton package instance with the given name. | |
136 | * | |
137 | * @param name The package name. | |
138 | * | |
139 | * @return The package instance. | |
140 | */ | |
141 | struct pkginfo * | |
142 | pkg_db_find_singleton(const char *name) | |
143 | { | |
144 | struct pkgset *set; | |
145 | struct pkginfo *pkg; | |
146 | ||
147 | set = pkg_db_find_set(name); | |
148 | pkg = pkg_db_get_singleton(set); | |
149 | if (pkg == NULL) | |
150 | ohshit(_("ambiguous package name '%s' with more " | |
151 | "than one installed instance"), set->name); | |
152 | ||
153 | return pkg; | |
154 | } | |
155 | ||
156 | /** | |
157 | * Return the package instance in a set with the given architecture. | |
158 | * | |
159 | * It traverse the various instances to find out whether there's one | |
160 | * matching the given architecture. If found, it returns it. Otherwise it | |
161 | * allocates a new instance and registers it in the package set before | |
162 | * returning it. | |
163 | * | |
164 | * @param set The package set to use. | |
165 | * @param arch The requested architecture. | |
166 | * | |
167 | * @return The package instance. | |
168 | */ | |
169 | struct pkginfo * | |
170 | pkg_db_get_pkg(struct pkgset *set, const struct dpkg_arch *arch) | |
171 | { | |
172 | struct pkginfo *pkg, **pkgp; | |
173 | ||
174 | assert(arch); | |
175 | assert(arch->type != DPKG_ARCH_NONE); | |
176 | ||
177 | pkg = &set->pkg; | |
178 | ||
179 | /* If there's a single unused slot, let's use that. */ | |
180 | if (pkg->installed.arch->type == DPKG_ARCH_NONE && pkg->arch_next == NULL) { | |
181 | pkg->installed.arch = arch; | |
182 | pkg->available.arch = arch; | |
183 | return pkg; | |
184 | } | |
185 | ||
186 | /* Match the slot with the most appropriate architecture. The installed | |
187 | * architecture always has preference over the available one, as there's | |
188 | * a small time window on cross-grades, where they might differ. */ | |
189 | for (pkgp = &pkg; *pkgp; pkgp = &(*pkgp)->arch_next) { | |
190 | if ((*pkgp)->installed.arch == arch) | |
191 | return *pkgp; | |
192 | } | |
193 | ||
194 | /* Need to create a new instance for the wanted architecture. */ | |
195 | pkg = nfmalloc(sizeof(struct pkginfo)); | |
196 | pkg_blank(pkg); | |
197 | pkg->set = set; | |
198 | pkg->arch_next = NULL; | |
199 | pkg->installed.arch = arch; | |
200 | pkg->available.arch = arch; | |
201 | *pkgp = pkg; | |
202 | npkg++; | |
203 | ||
204 | return pkg; | |
205 | } | |
206 | ||
207 | /** | |
208 | * Return the package instance with the given name and architecture. | |
209 | * | |
210 | * @param name The package name. | |
211 | * @param arch The requested architecture. | |
212 | * | |
213 | * @return The package instance. | |
214 | */ | |
215 | struct pkginfo * | |
216 | pkg_db_find_pkg(const char *name, const struct dpkg_arch *arch) | |
217 | { | |
218 | struct pkgset *set; | |
219 | struct pkginfo *pkg; | |
220 | ||
221 | set = pkg_db_find_set(name); | |
222 | pkg = pkg_db_get_pkg(set, arch); | |
223 | ||
224 | return pkg; | |
225 | } | |
226 | ||
227 | /** | |
228 | * Return the number of package sets available in the database. | |
229 | * | |
230 | * @return The number of package sets. | |
231 | */ | |
232 | int | |
233 | pkg_db_count_set(void) | |
234 | { | |
235 | return nset; | |
236 | } | |
237 | ||
238 | /** | |
239 | * Return the number of package instances available in the database. | |
240 | * | |
241 | * @return The number of package instances. | |
242 | */ | |
243 | int | |
244 | pkg_db_count_pkg(void) | |
245 | { | |
246 | return npkg; | |
247 | } | |
248 | ||
249 | struct pkgiterator { | |
250 | struct pkginfo *pkg; | |
251 | int nbinn; | |
252 | }; | |
253 | ||
254 | /** | |
255 | * Create a new package iterator. | |
256 | * | |
257 | * It can iterate either over package sets or over package instances. | |
258 | * | |
259 | * @return The iterator. | |
260 | */ | |
261 | struct pkgiterator * | |
262 | pkg_db_iter_new(void) | |
263 | { | |
264 | struct pkgiterator *iter; | |
265 | ||
266 | iter = m_malloc(sizeof(struct pkgiterator)); | |
267 | iter->pkg = NULL; | |
268 | iter->nbinn = 0; | |
269 | ||
270 | return iter; | |
271 | } | |
272 | ||
273 | /** | |
274 | * Return the next package set in the database. | |
275 | * | |
276 | * If no further package set is available, it will return NULL. | |
277 | * | |
278 | * @name iter The iterator. | |
279 | * | |
280 | * @return A package set. | |
281 | */ | |
282 | struct pkgset * | |
283 | pkg_db_iter_next_set(struct pkgiterator *iter) | |
284 | { | |
285 | struct pkgset *set; | |
286 | ||
287 | while (!iter->pkg) { | |
288 | if (iter->nbinn >= BINS) | |
289 | return NULL; | |
290 | if (bins[iter->nbinn]) | |
291 | iter->pkg = &bins[iter->nbinn]->pkg; | |
292 | iter->nbinn++; | |
293 | } | |
294 | ||
295 | set = iter->pkg->set; | |
296 | if (set->next) | |
297 | iter->pkg = &set->next->pkg; | |
298 | else | |
299 | iter->pkg = NULL; | |
300 | ||
301 | return set; | |
302 | } | |
303 | ||
304 | /** | |
305 | * Return the next package instance in the database. | |
306 | * | |
307 | * If no further package instance is available, it will return NULL. Note | |
308 | * that it will return all instances of a given package set in sequential | |
309 | * order. The first instance for a given package set will always correspond | |
310 | * to the native architecture even if that package is not installed or | |
311 | * available. | |
312 | * | |
313 | * @name iter The iterator. | |
314 | * | |
315 | * @return A package instance. | |
316 | */ | |
317 | struct pkginfo * | |
318 | pkg_db_iter_next_pkg(struct pkgiterator *iter) | |
319 | { | |
320 | struct pkginfo *pkg; | |
321 | ||
322 | while (!iter->pkg) { | |
323 | if (iter->nbinn >= BINS) | |
324 | return NULL; | |
325 | if (bins[iter->nbinn]) | |
326 | iter->pkg = &bins[iter->nbinn]->pkg; | |
327 | iter->nbinn++; | |
328 | } | |
329 | ||
330 | pkg = iter->pkg; | |
331 | if (pkg->arch_next) | |
332 | iter->pkg = pkg->arch_next; | |
333 | else if (pkg->set->next) | |
334 | iter->pkg = &pkg->set->next->pkg; | |
335 | else | |
336 | iter->pkg = NULL; | |
337 | ||
338 | return pkg; | |
339 | } | |
340 | ||
341 | /** | |
342 | * Free the package database iterator. | |
343 | * | |
344 | * @name iter The iterator. | |
345 | */ | |
346 | void | |
347 | pkg_db_iter_free(struct pkgiterator *iter) | |
348 | { | |
349 | free(iter); | |
350 | } | |
351 | ||
352 | void | |
353 | pkg_db_reset(void) | |
354 | { | |
355 | int i; | |
356 | ||
357 | dpkg_arch_reset_list(); | |
358 | nffreeall(); | |
359 | nset = 0; | |
360 | npkg = 0; | |
361 | for (i=0; i<BINS; i++) bins[i]= NULL; | |
362 | } | |
363 | ||
364 | void | |
365 | pkg_db_report(FILE *file) | |
366 | { | |
367 | int i, c; | |
368 | struct pkgset *pkg; | |
369 | int *freq; | |
370 | ||
371 | freq = m_malloc(sizeof(int) * nset + 1); | |
372 | for (i = 0; i <= nset; i++) | |
373 | freq[i] = 0; | |
374 | for (i=0; i<BINS; i++) { | |
375 | for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next); | |
376 | fprintf(file,"bin %5d has %7d\n",i,c); | |
377 | freq[c]++; | |
378 | } | |
379 | for (i = nset; i > 0 && freq[i] == 0; i--); | |
380 | while (i >= 0) { | |
381 | fprintf(file, "size %7d occurs %5d times\n", i, freq[i]); | |
382 | i--; | |
383 | } | |
384 | ||
385 | m_output(file, "<hash report>"); | |
386 | ||
387 | free(freq); | |
388 | } |