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