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