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