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