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