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 0;
 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 oa - ob;
 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->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 269         continue;               /* sources do not provide anything */
 270       if (pool->id2arch && (s->arch > pool->lastarch || !pool->id2arch[s->arch]))
 271         continue;               /* architecture not installable */
 272       pp = s->provides;
 273       if (!pp)                  /* solvable does not provide anything */
 274         continue;
 275       while ((id = *pp++) != ID_NULL)
 276         {
 277           if (ISRELDEP(id))
 278             {
 279               Reldep *rd = GETRELDEP(pool, id);
 280               id = rd->name;
 281             }
 282           whatprovides[id]++;          /* inc count of providers */
 283         }
 284     }
 285
 286   off = 2;      /* first entry is undef, second is empty list */
 287   idp = whatprovides;
 288   np = 0;                              /* number of names provided */
 289   for (i = 0; i < num; i++, idp++)
 290     {
 291       n = *idp;
 292       if (!n)                          /* no providers */
 293         continue;
 294       *idp = off;                      /* move from counts to offsets into whatprovidesdata */
 295       off += n + 1;                    /* make space for all providers + terminating ID_NULL */
 296       np++;                            /* inc # of provider 'slots' */
 297     }
 298
 299   if (pool->verbose)
 300     printf("provide ids: %d\n", np);
 301   extra = 2 * pool->nrels;
 302
 303   if (extra < 256)
 304     extra = 256;
 305
 306   if (pool->verbose)
 307     printf("provide space needed: %d + %d\n", off, extra);
 308
 309   /* alloc space for all providers + extra */
 310   whatprovidesdata = (Id *)xcalloc(off + extra, sizeof(Id));
 311
 312   /* now fill data for all provides */
 313   for (i = 1; i < pool->nsolvables; i++)
 314     {
 315       Id *pp;
 316       s = pool->solvables + i;
 317       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 318         continue;               /* sources do not provide anything */
 319       if (pool->id2arch && (s->arch > pool->lastarch || !pool->id2arch[s->arch]))
 320         continue;               /* architecture not installable */
 321       pp = s->provides;
 322       if (!pp)                         /* solvable does not provide anything */
 323         continue;
 324
 325       /* for all provides of this solvable */
 326       while ((id = *pp++) != 0)
 327         {
 328           if (ISRELDEP(id))
 329             {
 330               Reldep *rd = GETRELDEP(pool, id);
 331               id = rd->name;
 332             }
 333           d = whatprovidesdata + whatprovides[id];   /* offset into whatprovidesdata */
 334           if (*d)
 335             {
 336               d++;
 337               while (*d)               /* find free slot */
 338                 d++;
 339               if (d[-1] == i)
 340                 {
 341 #if 0
 342                   if (pool->verbose) printf("duplicate entry for %s in package %s.%s\n", id2str(pool, id), id2str(pool, s->name), id2str(pool, s->arch));
 343 #endif
 344                   continue;
 345                 }
 346             }
 347           *d = i;                      /* put solvable Id into data */
 348         }
 349     }
 350   pool->whatprovides = whatprovides;
 351   pool->whatprovidesdata = whatprovidesdata;
 352   pool->whatprovidesdataoff = off;
 353   pool->whatprovidesdataleft = extra;
 354   pool_shrink_whatprovides(pool);
 355 }
 356
 357 /******************************************************************************/
 358
 359 /*
 360  * pool_queuetowhatprovides
 361  *
 362  * on-demand filling of provider information
 363  * move queue data into whatprovidesdata
 364  * q: queue of Ids
 365  * returns: Offset into whatprovides
 366  */
 367
 368 Id
 369 pool_queuetowhatprovides(Pool *pool, Queue *q)
 370 {
 371   Offset off;
 372   int count = q->count;
 373
 374   if (count == 0)                      /* queue empty -> ID_EMPTY */
 375     return ID_EMPTY;
 376
 377   /* extend whatprovidesdata if needed, +1 for ID_NULL-termination */
 378   if (pool->whatprovidesdataleft < count + 1)
 379     {
 380       if (pool->verbose)
 381         printf("growing provides hash data...\n");
 382       pool->whatprovidesdata = (Id *)xrealloc(pool->whatprovidesdata, (pool->whatprovidesdataoff + count + 4096) * sizeof(Id));
 383       pool->whatprovidesdataleft = count + 4096;
 384     }
 385
 386   /* copy queue to next free slot */
 387   off = pool->whatprovidesdataoff;
 388   memcpy(pool->whatprovidesdata + pool->whatprovidesdataoff, q->elements, count * sizeof(Id));
 389
 390   /* adapt count and ID_NULL-terminate */
 391   pool->whatprovidesdataoff += count;
 392   pool->whatprovidesdata[pool->whatprovidesdataoff++] = ID_NULL;
 393   pool->whatprovidesdataleft -= count + 1;
 394
 395   return (Id)off;
 396 }
 397
 398
 399 /*
 400  * addrangedep
 401  *
 402  * add RangeDep to whatprovides
 403  * no exact providers, do range match
 404  *
 405  */
 406
 407 Id *
 408 addrelproviders(Pool *pool, Id d)
 409 {
 410   Reldep *rd = GETRELDEP(pool, d);
 411   Reldep *prd;
 412   Queue plist;
 413   Id buf[16];
 414   Id name = rd->name;
 415   Id evr = rd->evr;
 416   int flags = rd->flags;
 417   Id pid, *pidp;
 418   Id p, *pp, *pp2, *pp3;
 419
 420   d = GETRELID(pool, d);
 421   queueinit_buffer(&plist, buf, sizeof(buf)/sizeof(*buf));
 422   switch (flags)
 423     {
 424     case REL_AND:
 425     case REL_WITH:
 426       pp = GET_PROVIDESP(name, p);
 427       pp2 = GET_PROVIDESP(evr, p);
 428       while ((p = *pp++) != 0)
 429         {
 430           for (pp3 = pp2; *pp3;)
 431             if (*pp3++ == p)
 432               {
 433                 queuepush(&plist, p);
 434                 break;
 435               }
 436         }
 437       break;
 438     case REL_OR:
 439       pp = GET_PROVIDESP(name, p);
 440       while ((p = *pp++) != 0)
 441         queuepush(&plist, p);
 442       pp = GET_PROVIDESP(evr, p);
 443       while ((p = *pp++) != 0)
 444         queuepushunique(&plist, p);
 445       break;
 446     case REL_NAMESPACE:
 447 #if 0
 448       /* unknown namespace, just pass through */
 449       pp = GET_PROVIDESP(evr, p);
 450       while ((p = *pp++) != 0)
 451         queuepush(&plist, p);
 452 #endif
 453       break;
 454     default:
 455       break;
 456     }
 457
 458   /* convert to whatprovides id */
 459 #if 0
 460   if (pool->verbose)
 461     printf("addrelproviders: what provides %s?\n", id2str(pool, name));
 462 #endif
 463   if (flags && flags < 8)
 464     {
 465       FOR_PROVIDES(p, pp, name)
 466         {
 467 #if 0
 468           if (pool->verbose)
 469             printf("addrelproviders: checking package %s\n", id2str(pool, pool->p[p].name));
 470 #endif
 471           /* solvable p provides name in some rels */
 472           for (pidp = pool->solvables[p].provides; (pid = *pidp++) != 0; )
 473             {
 474               int pflags;
 475               Id pevr;
 476
 477               if (pid == name)
 478                 break;          /* yes, provides all versions */
 479               if (!ISRELDEP(pid))
 480                 continue;               /* wrong provides name */
 481               prd = GETRELDEP(pool, pid);
 482               if (prd->name != name)
 483                 continue;               /* wrong provides name */
 484               /* right package, both deps are rels */
 485               pflags = prd->flags;
 486               if (!pflags)
 487                 continue;
 488               if (flags == 7 || pflags == 7)
 489                 break; /* included */
 490               if ((pflags & flags & 5) != 0)
 491                 break; /* same direction, match */
 492               pevr = prd->evr;
 493               if (pevr == evr)
 494                 {
 495                   if ((pflags & flags & 2) != 0)
 496                     break; /* both have =, match */
 497                 }
 498               else
 499                 {
 500                   int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5);
 501                   if ((f & (1 << (1 + evrcmp(pool, pevr, evr)))) != 0)
 502                     break;
 503                 }
 504             }
 505           if (!pid)
 506             continue;   /* no rel match */
 507           queuepush(&plist, p);
 508         }
 509     }
 510   /* add providers to whatprovides */
 511 #if 0
 512   if (pool->verbose) printf("addrelproviders: adding %d packages to %d\n", plist.count, d);
 513 #endif
 514   pool->whatprovides[d] = pool_queuetowhatprovides(pool, &plist);
 515   queuefree(&plist);
 516
 517   return pool->whatprovidesdata + pool->whatprovides[d];
 518 }
 519
 520
 521 /*
 522  * return source of solvable
 523  * or NULL
 524  */
 525
 526 Source *
 527 pool_source(Pool *pool, Solvable *s)
 528 {
 529   int i;
 530   Source *source;
 531   int off = s - pool->solvables;
 532
 533   for (i = 0; i < pool->nsources; i++)
 534     {
 535       source = pool->sources[i];
 536       if (off >= source->start
 537           && off < source->start+source->nsolvables)
 538       {
 539         return source;
 540       }
 541     }
 542   return NULL;
 543 }
 544
 545 // EOF