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