src/pool.c

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