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 <stdarg.h>
  18 #include <unistd.h>
  19 #include <string.h>
  20
  21 #include "pool.h"
  22 #include "repo.h"
  23 #include "poolid.h"
  24 #include "poolid_private.h"
  25 #include "poolarch.h"
  26 #include "util.h"
  27 #include "bitmap.h"
  28 #include "evr.h"
  29
  30 #define SOLVABLE_BLOCK  255
  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
  37 static const char *initpool_data[] = {
  38   "<NULL>",                   // ID_NULL
  39   "",                         // ID_EMPTY
  40   "solvable:name",
  41   "solvable:arch",
  42   "solvable:evr",
  43   "solvable:vendor",
  44   "solvable:provides",
  45   "solvable:obsoletes",
  46   "solvable:conflicts",
  47   "solvable:requires",
  48   "solvable:recommends",
  49   "solvable:suggests",
  50   "solvable:supplements",
  51   "solvable:enhances",
  52   "solvable:freshens",
  53   "rpm:dbid",                          /* direct key into rpmdb */
  54   "solvable:prereqmarker",
  55   "solvable:filemarker",
  56   "namespace:installed",
  57   "namespace:modalias",
  58   "namespace:splitprovides",
  59   "namespace:language",
  60   "system:system",
  61   "src",
  62   "nosrc",
  63   "noarch",
  64   "repodata:external",
  65   "repodata:keys",
  66   "repodata:location",
  67   0
  68 };
  69
  70 /* create pool */
  71 Pool *
  72 pool_create(void)
  73 {
  74   Pool *pool;
  75   Solvable *s;
  76
  77   pool = (Pool *)sat_calloc(1, sizeof(*pool));
  78
  79   stringpool_init (&pool->ss, initpool_data);
  80
  81   /* alloc space for ReDep 0 */
  82   pool->rels = sat_extend_resize(0, 1, sizeof(Reldep), REL_BLOCK);
  83   pool->nrels = 1;
  84   memset(pool->rels, 0, sizeof(Reldep));
  85
  86   /* alloc space for Solvable 0 and system solvable */
  87   pool->solvables = sat_extend_resize(0, 2, sizeof(Solvable), SOLVABLE_BLOCK);
  88   pool->nsolvables = 2;
  89   memset(pool->solvables, 0, 2 * sizeof(Solvable));
  90   s = pool->solvables + SYSTEMSOLVABLE;
  91   s->name = SYSTEM_SYSTEM;
  92   s->arch = ARCH_NOARCH;
  93   s->evr = ID_EMPTY;
  94
  95   queue_init(&pool->vendormap);
  96
  97   pool->debugmask = SAT_DEBUG_RESULT;   /* FIXME */
  98   return pool;
  99 }
 100
 101
 102 /* free all the resources of our pool */
 103 void
 104 pool_free(Pool *pool)
 105 {
 106   int i;
 107
 108   pool_freewhatprovides(pool);
 109   pool_freeidhashes(pool);
 110   repo_freeallrepos(pool, 1);
 111   sat_free(pool->id2arch);
 112   sat_free(pool->solvables);
 113   sat_free(pool->ss.stringspace);
 114   sat_free(pool->ss.strings);
 115   sat_free(pool->rels);
 116   queue_free(&pool->vendormap);
 117   for (i = 0; i < DEP2STRBUF; i++)
 118     sat_free(pool->dep2strbuf[i]);
 119   sat_free(pool);
 120 }
 121
 122 Id
 123 pool_add_solvable(Pool *pool)
 124 {
 125   pool->solvables = sat_extend(pool->solvables, pool->nsolvables, 1, sizeof(Solvable), SOLVABLE_BLOCK);
 126   memset(pool->solvables + pool->nsolvables, 0, sizeof(Solvable));
 127   return pool->nsolvables++;
 128 }
 129
 130 Id
 131 pool_add_solvable_block(Pool *pool, int count)
 132 {
 133   Id nsolvables = pool->nsolvables;
 134   if (!count)
 135     return nsolvables;
 136   pool->solvables = sat_extend(pool->solvables, pool->nsolvables, count, sizeof(Solvable), SOLVABLE_BLOCK);
 137   memset(pool->solvables + nsolvables, 0, sizeof(Solvable) * count);
 138   pool->nsolvables += count;
 139   return nsolvables;
 140 }
 141
 142 void
 143 pool_free_solvable_block(Pool *pool, Id start, int count, int reuseids)
 144 {
 145   if (!count)
 146     return;
 147   if (reuseids && start + count == pool->nsolvables)
 148     {
 149       /* might want to shrink solvable array */
 150       pool->nsolvables = start;
 151       return;
 152     }
 153   memset(pool->solvables + start, 0, sizeof(Solvable) * count);
 154 }
 155
 156
 157 const char *
 158 solvable2str(Pool *pool, Solvable *s)
 159 {
 160   int l, nn = pool->dep2strn;
 161   const char *n, *e, *a;
 162   n = id2str(pool, s->name);
 163   e = id2str(pool, s->evr);
 164   a = id2str(pool, s->arch);
 165   l = strlen(n) + strlen(e) + strlen(a) + 3;
 166   if (l > pool->dep2strlen[nn])
 167     {
 168       pool->dep2strbuf[nn] = sat_realloc(pool->dep2strbuf[nn], l + 32);
 169       pool->dep2strlen[nn] = l + 32;
 170     }
 171   sprintf(pool->dep2strbuf[nn], "%s-%s.%s", n, e, a);
 172   pool->dep2strn = (nn + 1) % DEP2STRBUF;
 173   return pool->dep2strbuf[nn];
 174 }
 175
 176 static Pool *pool_shrink_whatprovides_sortcmp_data;
 177
 178 static int
 179 pool_shrink_whatprovides_sortcmp(const void *ap, const void *bp)
 180 {
 181   int r;
 182   Pool *pool = pool_shrink_whatprovides_sortcmp_data;
 183   Id oa, ob, *da, *db;
 184   oa = pool->whatprovides[*(Id *)ap];
 185   ob = pool->whatprovides[*(Id *)bp];
 186   if (oa == ob)
 187     return *(Id *)ap - *(Id *)bp;
 188   if (!oa)
 189     return -1;
 190   if (!ob)
 191     return 1;
 192   da = pool->whatprovidesdata + oa;
 193   db = pool->whatprovidesdata + ob;
 194   while (*db)
 195     if ((r = (*da++ - *db++)) != 0)
 196       return r;
 197   if (*da)
 198     return *da;
 199   return *(Id *)ap - *(Id *)bp;
 200 }
 201
 202 /*
 203  * pool_shrink_whatprovides  - unify whatprovides data
 204  *
 205  * whatprovides_rel must be empty for this to work!
 206  *
 207  */
 208 static void
 209 pool_shrink_whatprovides(Pool *pool)
 210 {
 211   Id i, id;
 212   Id *sorted;
 213   Id lastid, *last, *dp, *lp;
 214   Offset o;
 215   int r;
 216
 217   if (pool->ss.nstrings < 3)
 218     return;
 219   sorted = sat_malloc2(pool->ss.nstrings, sizeof(Id));
 220   for (id = 0; id < pool->ss.nstrings; id++)
 221     sorted[id] = id;
 222   pool_shrink_whatprovides_sortcmp_data = pool;
 223   qsort(sorted + 1, pool->ss.nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp);
 224   last = 0;
 225   lastid = 0;
 226   for (i = 1; i < pool->ss.nstrings; i++)
 227     {
 228       id = sorted[i];
 229       o = pool->whatprovides[id];
 230       if (o == 0 || o == 1)
 231         continue;
 232       dp = pool->whatprovidesdata + o;
 233       if (last)
 234         {
 235           lp = last;
 236           while (*dp)
 237             if (*dp++ != *lp++)
 238               {
 239                 last = 0;
 240                 break;
 241               }
 242           if (last && *lp)
 243             last = 0;
 244           if (last)
 245             {
 246               pool->whatprovides[id] = -lastid;
 247               continue;
 248             }
 249         }
 250       last = pool->whatprovidesdata + o;
 251       lastid = id;
 252     }
 253   sat_free(sorted);
 254   dp = pool->whatprovidesdata + 2;
 255   for (id = 1; id < pool->ss.nstrings; id++)
 256     {
 257       o = pool->whatprovides[id];
 258       if (o == 0 || o == 1)
 259         continue;
 260       if ((Id)o < 0)
 261         {
 262           i = -(Id)o;
 263           if (i >= id)
 264             abort();
 265           pool->whatprovides[id] = pool->whatprovides[i];
 266           continue;
 267         }
 268       lp = pool->whatprovidesdata + o;
 269       if (lp < dp)
 270         abort();
 271       pool->whatprovides[id] = dp - pool->whatprovidesdata;
 272       while ((*dp++ = *lp++) != 0)
 273         ;
 274     }
 275   o = dp - pool->whatprovidesdata;
 276   POOL_DEBUG(SAT_DEBUG_STATS, "shrunk whatprovidesdata from %d to %d\n", pool->whatprovidesdataoff, o);
 277   if (pool->whatprovidesdataoff == o)
 278     return;
 279   r = pool->whatprovidesdataoff - o;
 280   pool->whatprovidesdataoff = o;
 281   pool->whatprovidesdata = sat_realloc(pool->whatprovidesdata, (o + pool->whatprovidesdataleft) * sizeof(Id));
 282   if (r > pool->whatprovidesdataleft)
 283     r = pool->whatprovidesdataleft;
 284   memset(pool->whatprovidesdata + o, 0, r * sizeof(Id));
 285 }
 286
 287
 288 /*
 289  * pool_createwhatprovides()
 290  *
 291  * create hashes over pool of solvables to ease provide lookups
 292  *
 293  */
 294 void
 295 pool_createwhatprovides(Pool *pool)
 296 {
 297   int i, num, np, extra;
 298   Offset off;
 299   Solvable *s;
 300   Id id;
 301   Offset *idp, n;
 302   Offset *whatprovides;
 303   Id *whatprovidesdata, *d;
 304
 305   POOL_DEBUG(SAT_DEBUG_STATS, "number of solvables: %d\n", pool->nsolvables);
 306   POOL_DEBUG(SAT_DEBUG_STATS, "number of ids: %d + %d\n", pool->ss.nstrings, pool->nrels);
 307
 308   pool_freeidhashes(pool);      /* XXX: should not be here! */
 309   pool_freewhatprovides(pool);
 310   num = pool->ss.nstrings;
 311   pool->whatprovides = whatprovides = sat_extend_resize(0, num, sizeof(Offset), WHATPROVIDES_BLOCK);
 312   memset(whatprovides, 0, num * sizeof(Offset));
 313   pool->whatprovides_rel = sat_extend_resize(0, pool->nrels, sizeof(Offset), WHATPROVIDES_BLOCK);
 314   memset(pool->whatprovides_rel, 0, pool->nrels * sizeof(Offset));
 315
 316   /* count providers for each name */
 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       pp = s->repo->idarraydata + s->provides;
 326       while ((id = *pp++) != ID_NULL)
 327         {
 328           while (ISRELDEP(id))
 329             {
 330               Reldep *rd = GETRELDEP(pool, id);
 331               id = rd->name;
 332             }
 333           whatprovides[id]++;          /* inc count of providers */
 334         }
 335     }
 336
 337   off = 2;      /* first entry is undef, second is empty list */
 338   idp = whatprovides;
 339   np = 0;                              /* number of names provided */
 340   for (i = 0; i < num; i++, idp++)
 341     {
 342       n = *idp;
 343       if (!n)                          /* no providers */
 344         continue;
 345       *idp = off;                      /* move from counts to offsets into whatprovidesdata */
 346       off += n + 1;                    /* make space for all providers + terminating ID_NULL */
 347       np++;                            /* inc # of provider 'slots' */
 348     }
 349
 350   POOL_DEBUG(SAT_DEBUG_STATS, "provide ids: %d\n", np);
 351
 352   /* reserve some space for relation data */
 353   extra = 2 * pool->nrels;
 354   if (extra < 256)
 355     extra = 256;
 356
 357   POOL_DEBUG(SAT_DEBUG_STATS, "provide space needed: %d + %d\n", off, extra);
 358
 359   /* alloc space for all providers + extra */
 360   whatprovidesdata = sat_calloc(off + extra, sizeof(Id));
 361
 362   /* now fill data for all provides */
 363   for (i = 1; i < pool->nsolvables; i++)
 364     {
 365       Id *pp;
 366       s = pool->solvables + i;
 367       if (!s->provides)
 368         continue;
 369       if (!pool_installable(pool, s))
 370         continue;
 371
 372       /* for all provides of this solvable */
 373       pp = s->repo->idarraydata + s->provides;
 374       while ((id = *pp++) != 0)
 375         {
 376           while (ISRELDEP(id))
 377             {
 378               Reldep *rd = GETRELDEP(pool, id);
 379               id = rd->name;
 380             }
 381           d = whatprovidesdata + whatprovides[id];   /* offset into whatprovidesdata */
 382           if (*d)
 383             {
 384               d++;
 385               while (*d)               /* find free slot */
 386                 d++;
 387               if (d[-1] == i)
 388                 continue;
 389             }
 390           *d = i;                      /* put solvable Id into data */
 391         }
 392     }
 393   pool->whatprovidesdata = whatprovidesdata;
 394   pool->whatprovidesdataoff = off;
 395   pool->whatprovidesdataleft = extra;
 396   pool_shrink_whatprovides(pool);
 397 }
 398
 399 /*
 400  * free all of our whatprovides data
 401  * be careful, everything internalized with pool_queuetowhatprovides is gone, too
 402  */
 403 void
 404 pool_freewhatprovides(Pool *pool)
 405 {
 406   pool->whatprovides = sat_free(pool->whatprovides);
 407   pool->whatprovides_rel = sat_free(pool->whatprovides_rel);
 408   pool->whatprovidesdata = sat_free(pool->whatprovidesdata);
 409   pool->whatprovidesdataoff = 0;
 410   pool->whatprovidesdataleft = 0;
 411 }
 412
 413
 414 /******************************************************************************/
 415
 416 /*
 417  * pool_queuetowhatprovides  - add queue contents to whatprovidesdata
 418  *
 419  * on-demand filling of provider information
 420  * move queue data into whatprovidesdata
 421  * q: queue of Ids
 422  * returns: Offset into whatprovides
 423  *
 424  */
 425 Id
 426 pool_queuetowhatprovides(Pool *pool, Queue *q)
 427 {
 428   Offset off;
 429   int count = q->count;
 430
 431   if (count == 0)                      /* queue empty -> ID_EMPTY */
 432     return ID_EMPTY;
 433
 434   /* extend whatprovidesdata if needed, +1 for ID_NULL-termination */
 435   if (pool->whatprovidesdataleft < count + 1)
 436     {
 437       POOL_DEBUG(SAT_DEBUG_STATS, "growing provides hash data...\n");
 438       pool->whatprovidesdata = sat_realloc(pool->whatprovidesdata, (pool->whatprovidesdataoff + count + 4096) * sizeof(Id));
 439       pool->whatprovidesdataleft = count + 4096;
 440     }
 441
 442   /* copy queue to next free slot */
 443   off = pool->whatprovidesdataoff;
 444   memcpy(pool->whatprovidesdata + pool->whatprovidesdataoff, q->elements, count * sizeof(Id));
 445
 446   /* adapt count and ID_NULL-terminate */
 447   pool->whatprovidesdataoff += count;
 448   pool->whatprovidesdata[pool->whatprovidesdataoff++] = ID_NULL;
 449   pool->whatprovidesdataleft -= count + 1;
 450
 451   return (Id)off;
 452 }
 453
 454
 455 /*************************************************************************/
 456
 457 /*
 458  * addrelproviders
 459  *
 460  * add packages fulfilling the relation to whatprovides array
 461  * no exact providers, do range match
 462  *
 463  */
 464
 465 Id *
 466 pool_addrelproviders(Pool *pool, Id d)
 467 {
 468   Reldep *rd = GETRELDEP(pool, d);
 469   Reldep *prd;
 470   Queue plist;
 471   Id buf[16];
 472   Id name = rd->name;
 473   Id evr = rd->evr;
 474   int flags = rd->flags;
 475   Id pid, *pidp;
 476   Id p, *pp, *pp2, *pp3;
 477
 478   d = GETRELID(d);
 479   queue_init_buffer(&plist, buf, sizeof(buf)/sizeof(*buf));
 480   switch (flags)
 481     {
 482     case REL_AND:
 483     case REL_WITH:
 484       pp = pool_whatprovides(pool, name);
 485       pp2 = pool_whatprovides(pool, evr);
 486       while ((p = *pp++) != 0)
 487         {
 488           for (pp3 = pp2; *pp3;)
 489             if (*pp3++ == p)
 490               {
 491                 queue_push(&plist, p);
 492                 break;
 493               }
 494         }
 495       break;
 496     case REL_OR:
 497       pp = pool_whatprovides(pool, name);
 498       while ((p = *pp++) != 0)
 499         queue_push(&plist, p);
 500       pp = pool_whatprovides(pool, evr);
 501       while ((p = *pp++) != 0)
 502         queue_pushunique(&plist, p);
 503       break;
 504     case REL_NAMESPACE:
 505       if (pool->nscallback)
 506         {
 507           p = pool->nscallback(pool, pool->nscallbackdata, name, evr);
 508           if (p > 1)
 509             {
 510               queue_free(&plist);
 511               pool->whatprovides_rel[d] = p;
 512               return pool->whatprovidesdata + p;
 513             }
 514           if (p == 1)
 515             queue_push(&plist, SYSTEMSOLVABLE);
 516         }
 517       break;
 518     default:
 519       break;
 520     }
 521
 522   /* convert to whatprovides id */
 523 #if 0
 524   POOL_DEBUG(DEBUG_1, "addrelproviders: what provides %s?\n", id2str(pool, name));
 525 #endif
 526   if (flags && flags < 8)
 527     {
 528       FOR_PROVIDES(p, pp, name)
 529         {
 530 #if 0
 531           POOL_DEBUG(DEBUG_1, "addrelproviders: checking package %s\n", id2str(pool, pool->p[p].name));
 532 #endif
 533           /* solvable p provides name in some rels */
 534           pidp = pool->solvables[p].repo->idarraydata + pool->solvables[p].provides;
 535           while ((pid = *pidp++) != 0)
 536             {
 537               int pflags;
 538               Id pevr;
 539
 540               if (pid == name)
 541                 {
 542 #ifdef DEBIAN_SEMANTICS
 543                   continue;             /* unversioned provides can
 544                                          * never match versioned deps */
 545 #else
 546                   break;                /* yes, provides all versions */
 547 #endif
 548                 }
 549               if (!ISRELDEP(pid))
 550                 continue;               /* wrong provides name */
 551               prd = GETRELDEP(pool, pid);
 552               if (prd->name != name)
 553                 continue;               /* wrong provides name */
 554               /* right package, both deps are rels */
 555               pflags = prd->flags;
 556               if (!pflags)
 557                 continue;
 558               if (flags == 7 || pflags == 7)
 559                 break; /* included */
 560               if ((pflags & flags & 5) != 0)
 561                 break; /* same direction, match */
 562               pevr = prd->evr;
 563               if (pevr == evr)
 564                 {
 565                   if ((pflags & flags & 2) != 0)
 566                     break; /* both have =, match */
 567                 }
 568               else
 569                 {
 570                   int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5);
 571                   if ((f & (1 << (1 + evrcmp(pool, pevr, evr, EVRCMP_MATCH_RELEASE)))) != 0)
 572                     break;
 573                 }
 574             }
 575           if (!pid)
 576             continue;   /* no rel match */
 577           queue_push(&plist, p);
 578         }
 579       /* make our system solvable provide all unknown rpmlib() stuff */
 580       if (plist.count == 0 && !strncmp(id2str(pool, name), "rpmlib(", 7))
 581         queue_push(&plist, SYSTEMSOLVABLE);
 582     }
 583   /* add providers to whatprovides */
 584 #if 0
 585   POOL_DEBUG(DEBUG_1, "addrelproviders: adding %d packages to %d\n", plist.count, d);
 586 #endif
 587   pool->whatprovides_rel[d] = pool_queuetowhatprovides(pool, &plist);
 588   queue_free(&plist);
 589
 590   return pool->whatprovidesdata + pool->whatprovides_rel[d];
 591 }
 592
 593 /*************************************************************************/
 594
 595 void
 596 pool_debug(Pool *pool, int type, const char *format, ...)
 597 {
 598   va_list args;
 599   char buf[1024];
 600
 601   if ((type & (SAT_FATAL|SAT_ERROR)) == 0)
 602     {
 603       if ((pool->debugmask & type) == 0)
 604         return;
 605     }
 606   va_start(args, format);
 607   if (!pool->debugcallback)
 608     {
 609       if ((type & (SAT_FATAL|SAT_ERROR)) == 0)
 610         vprintf(format, args);
 611       else
 612         vfprintf(stderr, format, args);
 613       return;
 614     }
 615   vsnprintf(buf, sizeof(buf), format, args);
 616   pool->debugcallback(pool, pool->debugcallbackdata, type, buf);
 617 }
 618
 619 void
 620 pool_setdebuglevel(Pool *pool, int level)
 621 {
 622   int mask = SAT_DEBUG_RESULT;
 623   if (level > 0)
 624     mask |= SAT_DEBUG_STATS|SAT_DEBUG_ANALYZE|SAT_DEBUG_UNSOLVABLE;
 625   if (level > 1)
 626     mask |= SAT_DEBUG_JOB|SAT_DEBUG_SOLUTIONS|SAT_DEBUG_POLICY;
 627   if (level > 2)
 628     mask |= SAT_DEBUG_PROPAGATE;
 629   if (level > 3)
 630     mask |= SAT_DEBUG_RULE_CREATION;
 631   if (level > 4)
 632     mask |= SAT_DEBUG_SCHUBI;
 633   pool->debugmask = mask;
 634 }
 635
 636 /*************************************************************************/
 637
 638 struct searchfiles {
 639   Id *ids;
 640   char **dirs;
 641   char **names;
 642   int nfiles;
 643   Map seen;
 644 };
 645
 646 #define SEARCHFILES_BLOCK 127
 647
 648 static void
 649 pool_addfileprovides_dep(Pool *pool, Id *ida, struct searchfiles *sf, struct searchfiles *isf)
 650 {
 651   Id dep, sid;
 652   const char *s, *sr;
 653
 654   while ((dep = *ida++) != 0)
 655     {
 656       while (ISRELDEP(dep))
 657         {
 658           Reldep *rd;
 659           sid = pool->ss.nstrings + GETRELID(dep);
 660           if (MAPTST(&sf->seen, sid))
 661             {
 662               dep = 0;
 663               break;
 664             }
 665           MAPSET(&sf->seen, sid);
 666           rd = GETRELDEP(pool, dep);
 667           if (rd->flags < 8)
 668             dep = rd->name;
 669           else if (rd->flags == REL_NAMESPACE)
 670             {
 671               if (isf && (rd->name == NAMESPACE_INSTALLED || rd->name == NAMESPACE_SPLITPROVIDES))
 672                 {
 673                   sf = isf;
 674                   isf = 0;
 675                   if (MAPTST(&sf->seen, sid))
 676                     {
 677                       dep = 0;
 678                       break;
 679                     }
 680                   MAPSET(&sf->seen, sid);
 681                 }
 682               dep = rd->evr;
 683             }
 684           else
 685             {
 686               Id ids[2];
 687               ids[0] = rd->name;
 688               ids[1] = 0;
 689               pool_addfileprovides_dep(pool, ids, sf, isf);
 690               dep = rd->evr;
 691             }
 692         }
 693       if (!dep)
 694         continue;
 695       if (MAPTST(&sf->seen, dep))
 696         continue;
 697       MAPSET(&sf->seen, dep);
 698       s = id2str(pool, dep);
 699       if (*s != '/')
 700         continue;
 701       sf->ids = sat_extend(sf->ids, sf->nfiles, 1, sizeof(const char *), SEARCHFILES_BLOCK);
 702       sf->dirs = sat_extend(sf->dirs, sf->nfiles, 1, sizeof(const char *), SEARCHFILES_BLOCK);
 703       sf->names = sat_extend(sf->names, sf->nfiles, 1, sizeof(const char *), SEARCHFILES_BLOCK);
 704       sf->ids[sf->nfiles] = dep;
 705       sr = strrchr(s, '/');
 706       sf->names[sf->nfiles] = strdup(sr + 1);
 707       sf->dirs[sf->nfiles] = sat_malloc(sr - s + 1);
 708       if (sr != s)
 709         strncpy(sf->dirs[sf->nfiles], s, sr - s);
 710       sf->dirs[sf->nfiles][sr - s] = 0;
 711       sf->nfiles++;
 712     }
 713 }
 714
 715 struct addfileprovides_cbdata {
 716   int nfiles;
 717   Id *ids;
 718   char **dirs;
 719   char **names;
 720
 721   Repodata *olddata;
 722   Id *dids;
 723   Map useddirs;
 724 };
 725
 726 static int
 727 addfileprovides_cb(void *cbdata, Solvable *s, Repodata *data, Repokey *key, KeyValue *value)
 728 {
 729   struct addfileprovides_cbdata *cbd = cbdata;
 730   Pool *pool = s->repo->pool;
 731   int i;
 732   Id id;
 733
 734   if (data != cbd->olddata)
 735     {
 736       map_free(&cbd->useddirs);
 737       map_init(&cbd->useddirs, data->dirpool.ndirs);
 738       for (i = 0; i < cbd->nfiles; i++)
 739         {
 740           Id did = repodata_str2dir(data, cbd->dirs[i], 0);
 741           cbd->dids[i] = did;
 742           if (did)
 743             MAPSET(&cbd->useddirs, did);
 744         }
 745       cbd->olddata = data;
 746     }
 747   if (!MAPTST(&cbd->useddirs, value->id))
 748     return 0;
 749   for (i = 0; i < cbd->nfiles; i++)
 750     {
 751       if (cbd->dids[i] != value->id)
 752         continue;
 753       if (!strcmp(cbd->names[i], value->str))
 754         break;
 755     }
 756   if (i == cbd->nfiles)
 757     return 0;
 758   s->provides = repo_addid_dep(s->repo, s->provides, cbd->ids[i], SOLVABLE_FILEMARKER);
 759   return 0;
 760 }
 761
 762 void
 763 pool_addfileprovides(Pool *pool, Repo *installed)
 764 {
 765   Solvable *s;
 766   Repo *repo;
 767   struct searchfiles sf, isf;
 768   struct addfileprovides_cbdata cbd;
 769   int i;
 770   Id id_filelist;
 771
 772   id_filelist = str2id(pool, "filelist", 1);
 773
 774   memset(&sf, 0, sizeof(sf));
 775   map_init(&sf.seen, pool->ss.nstrings + pool->nrels);
 776   memset(&isf, 0, sizeof(isf));
 777   map_init(&isf.seen, pool->ss.nstrings + pool->nrels);
 778
 779   for (i = 1, s = pool->solvables + i; i < pool->nsolvables; i++, s++)
 780     {
 781       repo = s->repo;
 782       if (!repo)
 783         continue;
 784       if (s->obsoletes)
 785         pool_addfileprovides_dep(pool, repo->idarraydata + s->obsoletes, &sf, &isf);
 786       if (s->conflicts)
 787         pool_addfileprovides_dep(pool, repo->idarraydata + s->conflicts, &sf, &isf);
 788       if (s->requires)
 789         pool_addfileprovides_dep(pool, repo->idarraydata + s->requires, &sf, &isf);
 790       if (s->recommends)
 791         pool_addfileprovides_dep(pool, repo->idarraydata + s->recommends, &sf, &isf);
 792       if (s->suggests)
 793         pool_addfileprovides_dep(pool, repo->idarraydata + s->suggests, &sf, &isf);
 794       if (s->supplements)
 795         pool_addfileprovides_dep(pool, repo->idarraydata + s->supplements, &sf, &isf);
 796       if (s->enhances)
 797         pool_addfileprovides_dep(pool, repo->idarraydata + s->enhances, &sf, &isf);
 798       if (s->freshens)
 799         pool_addfileprovides_dep(pool, repo->idarraydata + s->freshens, &sf, &isf);
 800     }
 801   map_free(&sf.seen);
 802   map_free(&isf.seen);
 803   POOL_DEBUG(SAT_DEBUG_STATS, "found %d file dependencies\n", sf.nfiles);
 804   POOL_DEBUG(SAT_DEBUG_STATS, "found %d installed file dependencies\n", isf.nfiles);
 805   cbd.dids = 0;
 806   map_init(&cbd.useddirs, 1);
 807   if (sf.nfiles)
 808     {
 809 #if 0
 810       for (i = 0; i < sf.nfiles; i++)
 811         POOL_DEBUG(SAT_DEBUG_STATS, "looking up %s in filelist\n", id2str(pool, sf.ids[i]));
 812 #endif
 813       cbd.nfiles = sf.nfiles;
 814       cbd.ids = sf.ids;
 815       cbd.dirs = sf.dirs;
 816       cbd.names = sf.names;
 817       cbd.olddata = 0;
 818       cbd.dids = sat_realloc2(cbd.dids, sf.nfiles, sizeof(Id));
 819       pool_search(pool, 0, id_filelist, 0, 0, addfileprovides_cb, &cbd);
 820       sat_free(sf.ids);
 821       for (i = 0; i < sf.nfiles; i++)
 822         {
 823           sat_free(sf.dirs[i]);
 824           sat_free(sf.names[i]);
 825         }
 826       sat_free(sf.dirs);
 827       sat_free(sf.names);
 828     }
 829   if (isf.nfiles && installed)
 830     {
 831 #if 0
 832       for (i = 0; i < isf.nfiles; i++)
 833         POOL_DEBUG(SAT_DEBUG_STATS, "looking up %s in installed filelist\n", id2str(pool, isf.ids[i]));
 834 #endif
 835       cbd.nfiles = isf.nfiles;
 836       cbd.ids = isf.ids;
 837       cbd.dirs = isf.dirs;
 838       cbd.names = isf.names;
 839       cbd.olddata = 0;
 840       cbd.dids = sat_realloc2(cbd.dids, isf.nfiles, sizeof(Id));
 841       repo_search(installed, 0, id_filelist, 0, 0, addfileprovides_cb, &cbd);
 842       sat_free(isf.ids);
 843       for (i = 0; i < isf.nfiles; i++)
 844         {
 845           sat_free(isf.dirs[i]);
 846           sat_free(isf.names[i]);
 847         }
 848       sat_free(isf.dirs);
 849       sat_free(isf.names);
 850     }
 851   map_free(&cbd.useddirs);
 852   sat_free(cbd.dids);
 853   pool_freewhatprovides(pool);  /* as we have added provides */
 854 }
 855
 856 #if 0
 857
 858 struct mountpoint {
 859   const char *path;
 860   int kbytes;
 861   int files;
 862 };
 863
 864 struct mptree {
 865   Id sibling;
 866   Id child;
 867   const char *comp;
 868   int compl;
 869   Id mountpoint;
 870 };
 871
 872 struct cbdata {
 873   struct mountpoint *mps;
 874   Id *dirmap;
 875   int nmap;
 876 };
 877
 878 static int
 879 pool_fill_DU_add_cb(void *data, Solvable *s, Id key, const char *str)
 880 {
 881   struct cbdata *cbdata = data;
 882   Id mp, dirnum, kbytes, files;
 883
 884   dp = data_read_id(dp, &dirnum);
 885   dp = data_read_id(dp, &kbytes);
 886   data_read_id(dp, &files);
 887   if (dirnum < 0 || dirnum > cbdata->nmap)
 888     return 0;
 889   mp = cbdata->dirmap[dirnum];
 890   if (mp >= 0)
 891     {
 892       cbdata->mps[mp].kbytes += kbytes;
 893       cbdata->mps[mp].files += files;
 894     }
 895   return 0;
 896 }
 897
 898 static int
 899 pool_fill_DU_sub_cb(void *data, Solvable *s, Id key, const char *str)
 900 {
 901   struct cbdata *cbdata = data;
 902   Id mp, dirnum, kbytes, files;
 903
 904   dp = data_read_id(dp, &dirnum);
 905   dp = data_read_id(dp, &kbytes);
 906   data_read_id(dp, &files);
 907   if (dirnum < 0 || dirnum > cbdata->nmap)
 908     return 0;
 909   mp = cbdata->dirmap[dirnum];
 910   if (mp >= 0)
 911     {
 912       cbdata->mps[mp].kbytes -= kbytes;
 913       cbdata->mps[mp].files -= files;
 914     }
 915   return 0;
 916 }
 917
 918 static void
 919 propagate_mountpoints(struct mptree *mptree, int pos, Id mountpoint)
 920 {
 921   int i;
 922   if (mptree[pos].mountpoint == -1)
 923     mptree[pos].mountpoint = mountpoint;
 924   else
 925     mountpoint = mptree[pos].mountpoint;
 926   for (i = mptree[pos].child; i; i = mptree[i].sibling)
 927     propagate_mountpoints(mptree, i, mountpoint);
 928 }
 929
 930 void
 931 pool_fill_DU(Pool *pool, struct mountpoint *mps, int nmps)
 932 {
 933   char *path, *p;
 934   Id *dirmap;
 935   struct mptree *mptree;
 936   int nmptree;
 937   int pos;
 938   int mp;
 939
 940   struct matchdata md;
 941   struct cbdata cbdata;
 942
 943   memset(&md, 0, sizeof(md));
 944   md.pool = 0;
 945   md.matchstr = 0;
 946   md.flags = 0;
 947   md.callback = 0;
 948   md.callback_data = &cbdata
 949
 950   cbdata.mps = mps;
 951   cbdata.dirmap = 0;
 952   cbdata.nmap = 0;
 953
 954   mptree = sat_malloc2(16, sizeof(mptree));
 955
 956   /* our root node */
 957   mptree[0].sibling = 0;
 958   mptree[0].child = 0;
 959   mptree[0].comp = 0;
 960   mptree[0].compl = 0;
 961   mptree[0].mountpoint = -1;
 962   nmptree = 1;
 963
 964   /* create component tree */
 965   for (mp = 0; mp < nmps; mp++)
 966     {
 967       pos = 0;
 968       path = mps[mp].path;
 969       while(*path == '/')
 970         path++;
 971       while (*path)
 972         {
 973           if ((p = strchr('/', path)) == 0)
 974             {
 975               comp = path;
 976               compl = strlen(comp);
 977               path += compl;
 978             }
 979           else
 980             {
 981               comp = path;
 982               compl = p - path;
 983               path = p + 1;
 984               while(*path == '/')
 985                 path++;
 986             }
 987           for (i = mptree[pos].child; i; i = mptree[i].sibling)
 988             if (mptree[i].compl == compl && !strncmp(mptree[i].comp, comp, compl))
 989               break;
 990           if (!i)
 991             {
 992               /* create new node */
 993               if ((nmptree & 15) == 0)
 994                 mptree = sat_realloc2(mptree, nmptree + 16, sizeof(mptree));
 995               i = nmptree++;
 996               mptree[i].sibling = mptree[pos].child;
 997               mptree[i].child = 0;
 998               mptree[i].comp = comp;
 999               mptree[i].compl = compl;
1000               mptree[i].mountpoint = -1;
1001               mptree[pos].child = i;
1002             }
1003           pos = i;
1004         }
1005       mptree[pos].mountpoint = mp;
1006     }
1007   propagate_mountpoints(mptree, 0, mptree[0].mountpoint);
1008
1009   for_all_repos
1010     {
1011       for_all_repodatas_containing_DU
1012         {
1013           /* create map from dir to mptree */
1014           dirmap = xcalloc2(pool->ndirs, sizeof(Id));
1015           mp = 0;
1016           for (dn = 2, dirs = pool->dirs + dn; dn < pool->ndirs; dn++)
1017             {
1018               id = *dirs++;
1019               if (id <= 0)
1020                 {
1021                   mp = dirmap[-id];
1022                   continue;
1023                 }
1024               if (mp < 0)
1025                 {
1026                   /* unconnected */
1027                   dirmap[dn] = mp;
1028                   continue;
1029                 }
1030               if (!mptree[mp].child)
1031                 {
1032                   dirmap[dn] = -mp;
1033                   continue;
1034                 }
1035               comp = id2str(pool, id);
1036               compl = strlen(comp);
1037               for (i = mptree[mp].child; i; i = mptree[i].sibling)
1038                 if (mptree[i].compl == compl && !strncmp(mptree[i].comp, comp, compl))
1039                   break;
1040               dirmap[dn] = i ? i : -mp;
1041             }
1042           /* change dirmap to point to mountpoint instead of mptree */
1043           for (dn = 0; dn < pool->ndirs; dn++)
1044             {
1045               mp = dirmap[i];
1046               dirmap[i] = mptree[mp > 0 ? mp : -mp].mountpoint;
1047             }
1048
1049           cbdata.nmap = pool->ndirs;
1050           cbdata.dirmap = dirmap;
1051
1052           md.callback = pool_fill_DU_add_cb;
1053           for_solvables_to_be_installed()
1054             {
1055               if (p < data->start || p >= data->end)
1056                 continue;
1057               repodata_search(data, p - data->start, SOLVABLE_DUDATA, &md);
1058             }
1059           md.callback = pool_fill_DU_sub_cb;
1060           for_solvables_to_be_erased()
1061             {
1062               if (p < data->start || p >= data->end)
1063                 continue;
1064               repodata_search(data, p - data->start, SOLVABLE_DUDATA, &md);
1065             }
1066
1067           cbdata.dirmap = 0;
1068           cbdata.nmap = 0;
1069           sat_free(dirmap);
1070         }
1071     }
1072 }
1073
1074 #endif
1075
1076 void pool_search(Pool *pool, Id p, Id key, const char *match, int flags, int (*callback)(void *cbdata, Solvable *s, struct _Repodata *data, struct _Repokey *key, struct _KeyValue *kv), void *cbdata)
1077 {
1078   if (p)
1079     {
1080       if (pool->solvables[p].repo)
1081         repo_search(pool->solvables[p].repo, p, key, match, flags, callback, cbdata);
1082       return;
1083     }
1084   /* FIXME: obey callback return value! */
1085   for (p = 1; p < pool->nsolvables; p++)
1086     if (pool->solvables[p].repo)
1087       repo_search(pool->solvables[p].repo, p, key, match, flags, callback, cbdata);
1088 }
1089
1090 // EOF