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