- some more cleanup
[platform/upstream/libsolv.git] / src / pool.c
1 /*
2  * Copyright (c) 2007, Novell Inc.
3  *
4  * This program is licensed under the BSD license, read LICENSE.BSD
5  * for further information
6  */
7
8 /*
9  * pool.c
10  * 
11  * The pool contains information about solvables
12  * stored optimized for memory consumption and fast retrieval.
13  */
14
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <unistd.h>
18 #include <string.h>
19
20 #include "pool.h"
21 #include "repo.h"
22 #include "poolid.h"
23 #include "poolid_private.h"
24 #include "poolarch.h"
25 #include "util.h"
26 #include "evr.h"
27
28 #define SOLVABLE_BLOCK  255
29
30 // reset all whatprovides
31 // 
32 void
33 pool_freewhatprovides(Pool *pool)
34 {
35   pool->whatprovides = xfree(pool->whatprovides);
36   pool->whatprovidesdata = xfree(pool->whatprovidesdata);
37   pool->whatprovidesdataoff = 0;
38   pool->whatprovidesdataleft = 0;
39 }
40
41
42 // list of string constants, so we can do pointer/Id instead of string comparison
43 // index into array matches ID_xxx constants in pool.h
44
45 static const char *initpool_data[] = {
46   "<NULL>",                   // ID_NULL
47   "",                         // ID_EMPTY
48   "solvable:name",
49   "solvable:arch",
50   "solvable:evr",
51   "solvable:vendor",
52   "solvable:provides",
53   "solvable:obsoletes",
54   "solvable:conflicts",
55   "solvable:requires",
56   "solvable:recommends",
57   "solvable:suggests",
58   "solvable:supplements",
59   "solvable:enhances",
60   "solvable:freshens",
61   "rpm:dbid",                          /* direct key into rpmdb */
62   "solvable:prereqmarker",
63   "solvable:filemarker",
64   "namespace:installed",
65   "namespace:modalias",
66   "system:system",
67   "src",
68   "nosrc",
69   "noarch",
70   0
71 };
72
73 // create pool
74 // 
75 Pool *
76 pool_create(void)
77 {
78   Pool *pool;
79   Solvable *s;
80
81   pool = (Pool *)xcalloc(1, sizeof(*pool));
82
83   stringpool_init (&pool->ss, initpool_data);
84
85   // pre-alloc space for a RelDep
86   pool->rels = (Reldep *)xcalloc(1 + REL_BLOCK, sizeof(Reldep));
87   pool->nrels = 1;
88
89   // pre-alloc space for a Solvable
90   pool->solvables = (Solvable *)xcalloc(SOLVABLE_BLOCK + 1, sizeof(Solvable));
91   pool->nsolvables = 2;
92   queue_init(&pool->vendormap);
93   s = pool->solvables + SYSTEMSOLVABLE;
94   s->name = SYSTEM_SYSTEM;
95   s->arch = ARCH_NOARCH;
96   s->evr = ID_EMPTY;
97   return pool;
98 }
99
100
101 // empty the pool
102 // 
103 void
104 pool_free(Pool *pool)
105 {
106   int i;
107
108   pool_freewhatprovides(pool);
109   pool_freeidhashes(pool);
110   repo_freeallrepos(pool, 1);
111   xfree(pool->id2arch);
112   xfree(pool->solvables);
113   xfree(pool->ss.stringspace);
114   xfree(pool->ss.strings);
115   xfree(pool->rels);
116   queue_free(&pool->vendormap);
117   for (i = 0; i < DEP2STRBUF; i++)
118     xfree(pool->dep2strbuf[i]);
119   xfree(pool);
120 }
121
122 Id
123 pool_add_solvable(Pool *pool)
124 {
125   if ((pool->nsolvables & SOLVABLE_BLOCK) == 0)
126     pool->solvables = xrealloc2(pool->solvables, pool->nsolvables + (SOLVABLE_BLOCK + 1), sizeof(Solvable));
127   memset(pool->solvables + pool->nsolvables, 0, sizeof(Solvable));
128   return pool->nsolvables++;
129 }
130
131 Id
132 pool_add_solvable_block(Pool *pool, int count)
133 {
134   Id nsolvables = pool->nsolvables;
135   if (!count)
136     return nsolvables;
137   if (((nsolvables - 1) | SOLVABLE_BLOCK) != ((nsolvables + count - 1) | SOLVABLE_BLOCK))
138     pool->solvables = xrealloc2(pool->solvables, (nsolvables + count + SOLVABLE_BLOCK) & ~SOLVABLE_BLOCK, sizeof(Solvable));
139   memset(pool->solvables + nsolvables, 0, sizeof(Solvable) * count);
140   pool->nsolvables += count;
141   return nsolvables;
142 }
143
144 void
145 pool_free_solvable_block(Pool *pool, Id start, int count, int reuseids)
146 {
147   if (!count)
148     return;
149   if (reuseids && start + count == pool->nsolvables)
150     {
151       /* might want to shrink solvable array */
152       pool->nsolvables = start;
153       return;
154     }
155   memset(pool->solvables + start, 0, sizeof(Solvable) * count);
156 }
157
158 static Pool *pool_shrink_whatprovides_sortcmp_data;
159
160 static int
161 pool_shrink_whatprovides_sortcmp(const void *ap, const void *bp)
162 {
163   int r;
164   Pool *pool = pool_shrink_whatprovides_sortcmp_data;
165   Id oa, ob, *da, *db;
166   oa = pool->whatprovides[*(Id *)ap];
167   ob = pool->whatprovides[*(Id *)bp];
168   if (oa == ob)
169     return *(Id *)ap - *(Id *)bp;
170   if (!oa)
171     return -1;
172   if (!ob)
173     return 1;
174   da = pool->whatprovidesdata + oa;
175   db = pool->whatprovidesdata + ob;
176   while (*db)
177     if ((r = (*da++ - *db++)) != 0)
178       return r;
179   if (*da)
180     return *da;
181   return *(Id *)ap - *(Id *)bp;
182 }
183
184 static void
185 pool_shrink_whatprovides(Pool *pool)
186 {
187   Id i, id;
188   Id *sorted;
189   Id lastid, *last, *dp, *lp;
190   Offset o;
191   int r;
192
193   if (pool->ss.nstrings < 3)
194     return;
195   sorted = xmalloc2(pool->ss.nstrings, sizeof(Id));
196   for (id = 0; id < pool->ss.nstrings; id++)
197     sorted[id] = id;
198   pool_shrink_whatprovides_sortcmp_data = pool;
199   qsort(sorted + 1, pool->ss.nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp);
200   last = 0;
201   lastid = 0;
202   for (i = 1; i < pool->ss.nstrings; i++)
203     {
204       id = sorted[i];
205       o = pool->whatprovides[id];
206       if (o == 0 || o == 1)
207         continue;
208       dp = pool->whatprovidesdata + o;
209       if (last)
210         {
211           lp = last;
212           while (*dp)   
213             if (*dp++ != *lp++)
214               {
215                 last = 0;
216                 break;
217               }
218           if (last && *lp)
219             last = 0;
220           if (last)
221             {
222               pool->whatprovides[id] = -lastid;
223               continue;
224             }
225         }
226       last = pool->whatprovidesdata + o;
227       lastid = id;
228     }
229   xfree(sorted);
230   dp = pool->whatprovidesdata + 2;
231   for (id = 1; id < pool->ss.nstrings; id++)
232     {
233       o = pool->whatprovides[id];
234       if (o == 0 || o == 1)
235         continue;
236       if ((Id)o < 0)
237         {
238           i = -(Id)o;
239           if (i >= id)
240             abort();
241           pool->whatprovides[id] = pool->whatprovides[i];
242           continue;
243         }
244       lp = pool->whatprovidesdata + o;
245       if (lp < dp)
246         abort();
247       pool->whatprovides[id] = dp - pool->whatprovidesdata;
248       while ((*dp++ = *lp++) != 0)
249         ;
250     }
251   o = dp - pool->whatprovidesdata;
252   if (pool->verbose)
253     printf("shrunk whatprovidesdata from %d to %d\n", pool->whatprovidesdataoff, o);
254   if (pool->whatprovidesdataoff == o)
255     return;
256   r = pool->whatprovidesdataoff - o;
257   pool->whatprovidesdataoff = o;
258   pool->whatprovidesdata = xrealloc(pool->whatprovidesdata, (o + pool->whatprovidesdataleft) * sizeof(Id));
259   if (r > pool->whatprovidesdataleft)
260     r = pool->whatprovidesdataleft;
261   memset(pool->whatprovidesdata + o, 0, r * sizeof(Id));
262 }
263
264
265 /*
266  * pool_createwhatprovides()
267  * 
268  * create hashes over complete pool to ease lookups
269  * 
270  */
271
272 void
273 pool_createwhatprovides(Pool *pool)
274 {
275   int i, num, np, extra;
276   Offset off;
277   Solvable *s;
278   Id id;
279   Offset *idp, n;
280   Offset *whatprovides;
281   Id *whatprovidesdata, *d;
282
283   if (pool->verbose)
284     printf("number of solvables: %d\n", pool->nsolvables);
285   if (pool->verbose)
286     printf("number of ids: %d + %d\n", pool->ss.nstrings, pool->nrels);
287
288   pool_freeidhashes(pool);
289   pool_freewhatprovides(pool);
290   num = pool->ss.nstrings + pool->nrels;
291   whatprovides = (Offset *)xcalloc(num, sizeof(Offset));
292
293   /* count providers for each name */
294   for (i = 1; i < pool->nsolvables; i++)
295     {
296       Id *pp;
297       s = pool->solvables + i;
298       if (!s->provides)
299         continue;
300       if (!pool_installable(pool, s))
301         continue;
302       pp = s->repo->idarraydata + s->provides;
303       while ((id = *pp++) != ID_NULL)
304         {
305           if (ISRELDEP(id))
306             {
307               Reldep *rd = GETRELDEP(pool, id);
308               id = rd->name;
309             }
310           whatprovides[id]++;          /* inc count of providers */
311         }
312     }
313
314   off = 2;      /* first entry is undef, second is empty list */
315   idp = whatprovides;
316   np = 0;                              /* number of names provided */
317   for (i = 0; i < num; i++, idp++)
318     {
319       n = *idp;
320       if (!n)                          /* no providers */
321         continue;
322       *idp = off;                      /* move from counts to offsets into whatprovidesdata */
323       off += n + 1;                    /* make space for all providers + terminating ID_NULL */
324       np++;                            /* inc # of provider 'slots' */
325     }
326
327   if (pool->verbose)
328     printf("provide ids: %d\n", np);
329   extra = 2 * pool->nrels;
330
331   if (extra < 256)
332     extra = 256;
333
334   if (pool->verbose)
335     printf("provide space needed: %d + %d\n", off, extra);
336
337   /* alloc space for all providers + extra */
338   whatprovidesdata = (Id *)xcalloc(off + extra, sizeof(Id));
339
340   /* now fill data for all provides */
341   for (i = 1; i < pool->nsolvables; i++)
342     {
343       Id *pp;
344       s = pool->solvables + i;
345       if (!s->provides)
346         continue;
347       if (!pool_installable(pool, s))
348         continue;
349
350       /* for all provides of this solvable */
351       pp = s->repo->idarraydata + s->provides;
352       while ((id = *pp++) != 0)
353         {
354           if (ISRELDEP(id))
355             {
356               Reldep *rd = GETRELDEP(pool, id);
357               id = rd->name;
358             }
359           d = whatprovidesdata + whatprovides[id];   /* offset into whatprovidesdata */
360           if (*d)
361             {
362               d++;
363               while (*d)               /* find free slot */
364                 d++;
365               if (d[-1] == i)
366                 {
367 #if 0
368                   if (pool->verbose) printf("duplicate entry for %s in package %s.%s\n", id2str(pool, id), id2str(pool, s->name), id2str(pool, s->arch));
369 #endif
370                   continue;
371                 }
372             }
373           *d = i;                      /* put solvable Id into data */
374         }
375     }
376   pool->whatprovides = whatprovides;
377   pool->whatprovidesdata = whatprovidesdata;
378   pool->whatprovidesdataoff = off;
379   pool->whatprovidesdataleft = extra;
380   pool_shrink_whatprovides(pool);
381 }
382
383
384 /******************************************************************************/
385
386 /*
387  * pool_queuetowhatprovides
388  * 
389  * on-demand filling of provider information
390  * move queue data into whatprovidesdata
391  * q: queue of Ids
392  * returns: Offset into whatprovides
393  */
394
395 Id
396 pool_queuetowhatprovides(Pool *pool, Queue *q)
397 {
398   Offset off;
399   int count = q->count;
400
401   if (count == 0)                      /* queue empty -> ID_EMPTY */
402     return ID_EMPTY;
403
404   /* extend whatprovidesdata if needed, +1 for ID_NULL-termination */
405   if (pool->whatprovidesdataleft < count + 1)
406     {
407       if (pool->verbose)
408         printf("growing provides hash data...\n");
409       pool->whatprovidesdata = (Id *)xrealloc(pool->whatprovidesdata, (pool->whatprovidesdataoff + count + 4096) * sizeof(Id));
410       pool->whatprovidesdataleft = count + 4096;
411     }
412
413   /* copy queue to next free slot */
414   off = pool->whatprovidesdataoff;
415   memcpy(pool->whatprovidesdata + pool->whatprovidesdataoff, q->elements, count * sizeof(Id));
416
417   /* adapt count and ID_NULL-terminate */
418   pool->whatprovidesdataoff += count;
419   pool->whatprovidesdata[pool->whatprovidesdataoff++] = ID_NULL;
420   pool->whatprovidesdataleft -= count + 1;
421
422   return (Id)off;
423 }
424
425
426 /******************************************************************************/
427
428 /*
429  * addrelproviders
430  * 
431  * add packages fulfilling the relation to whatprovides array
432  * no exact providers, do range match
433  * 
434  */
435
436 Id *
437 pool_addrelproviders(Pool *pool, Id d)
438 {
439   Reldep *rd = GETRELDEP(pool, d);
440   Reldep *prd;
441   Queue plist;
442   Id buf[16];
443   Id name = rd->name;
444   Id evr = rd->evr;
445   int flags = rd->flags;
446   Id pid, *pidp;
447   Id p, *pp, *pp2, *pp3;
448
449   d = GETRELID(pool, d);
450   queue_init_buffer(&plist, buf, sizeof(buf)/sizeof(*buf));
451   switch (flags)
452     {
453     case REL_AND:
454     case REL_WITH:
455       pp = pool_whatprovides(pool, name);
456       pp2 = pool_whatprovides(pool, evr);
457       while ((p = *pp++) != 0)
458         {
459           for (pp3 = pp2; *pp3;)
460             if (*pp3++ == p)
461               {
462                 queue_push(&plist, p);
463                 break;
464               }
465         }
466       break;
467     case REL_OR:
468       pp = pool_whatprovides(pool, name);
469       while ((p = *pp++) != 0)
470         queue_push(&plist, p);
471       pp = pool_whatprovides(pool, evr);
472       while ((p = *pp++) != 0)
473         queue_pushunique(&plist, p);
474       break;
475     case REL_NAMESPACE:
476       if (pool->nscallback)
477         {
478           p = pool->nscallback(pool, pool->nscallbackdata, name, evr);
479           if (p > 1)
480             {
481               queue_free(&plist);
482               pool->whatprovides[d] = p;
483               return pool->whatprovidesdata + p;
484             }
485           if (p == 1)
486             queue_push(&plist, SYSTEMSOLVABLE);
487         }
488       break;
489     default:
490       break;
491     }
492
493   /* convert to whatprovides id */
494 #if 0
495   if (pool->verbose)
496     printf("addrelproviders: what provides %s?\n", id2str(pool, name));
497 #endif
498   if (flags && flags < 8)
499     {
500       FOR_PROVIDES(p, pp, name)
501         {
502 #if 0
503           if (pool->verbose)
504             printf("addrelproviders: checking package %s\n", id2str(pool, pool->p[p].name));
505 #endif
506           /* solvable p provides name in some rels */
507           pidp = pool->solvables[p].repo->idarraydata + pool->solvables[p].provides;
508           while ((pid = *pidp++) != 0)
509             {
510               int pflags;
511               Id pevr;
512
513               if (pid == name)
514                 break;          /* yes, provides all versions */
515               if (!ISRELDEP(pid))
516                 continue;               /* wrong provides name */
517               prd = GETRELDEP(pool, pid);
518               if (prd->name != name)
519                 continue;               /* wrong provides name */
520               /* right package, both deps are rels */
521               pflags = prd->flags;
522               if (!pflags)
523                 continue;
524               if (flags == 7 || pflags == 7)
525                 break; /* included */
526               if ((pflags & flags & 5) != 0)
527                 break; /* same direction, match */
528               pevr = prd->evr;
529               if (pevr == evr)
530                 {
531                   if ((pflags & flags & 2) != 0)
532                     break; /* both have =, match */
533                 }
534               else
535                 {
536                   int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5);
537                   if ((f & (1 << (1 + evrcmp(pool, pevr, evr)))) != 0)
538                     break;
539                 }
540             }
541           if (!pid)
542             continue;   /* no rel match */
543           queue_push(&plist, p);
544         }
545       /* make our system solvable provide all unknown rpmlib() stuff */
546       if (plist.count == 0 && !strncmp(id2str(pool, name), "rpmlib(", 7))
547         queue_push(&plist, SYSTEMSOLVABLE);
548     }
549   /* add providers to whatprovides */
550 #if 0
551   if (pool->verbose) printf("addrelproviders: adding %d packages to %d\n", plist.count, d);
552 #endif
553   pool->whatprovides[d] = pool_queuetowhatprovides(pool, &plist);
554   queue_free(&plist);
555
556   return pool->whatprovidesdata + pool->whatprovides[d];
557 }
558
559 // EOF