src/pool.c

   1 /*
   2  * Copyright (c) 2007-2009, 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 #define KNOWNID_INITIALIZE
  33 #include "knownid.h"
  34 #undef KNOWNID_INITIALIZE
  35
  36 /* create pool */
  37 Pool *
  38 pool_create(void)
  39 {
  40   Pool *pool;
  41   Solvable *s;
  42
  43   pool = (Pool *)solv_calloc(1, sizeof(*pool));
  44
  45   stringpool_init (&pool->ss, initpool_data);
  46
  47   /* alloc space for RelDep 0 */
  48   pool->rels = solv_extend_resize(0, 1, sizeof(Reldep), REL_BLOCK);
  49   pool->nrels = 1;
  50   memset(pool->rels, 0, sizeof(Reldep));
  51
  52   /* alloc space for Solvable 0 and system solvable */
  53   pool->solvables = solv_extend_resize(0, 2, sizeof(Solvable), SOLVABLE_BLOCK);
  54   pool->nsolvables = 2;
  55   memset(pool->solvables, 0, 2 * sizeof(Solvable));
  56
  57   /* initialize the system solvable */
  58   s = pool->solvables + SYSTEMSOLVABLE;
  59   s->name = SYSTEM_SYSTEM;
  60   s->arch = ARCH_NOARCH;
  61   s->evr = ID_EMPTY;
  62
  63   queue_init(&pool->vendormap);
  64
  65   pool->debugmask = SOLV_DEBUG_RESULT;  /* FIXME */
  66 #ifdef FEDORA
  67   pool->obsoleteusescolors = 1;
  68 #endif
  69 #ifdef DEBIAN
  70   pool->allowselfconflicts = 1;
  71 # ifdef MULTI_SEMANTICS
  72   pool->disttype = DISTTYPE_DEB;
  73 # endif
  74 #endif
  75 #ifdef RPM5
  76   pool->obsoleteusesprovides = 1;
  77   pool->implicitobsoleteusesprovides = 1;
  78 #endif
  79   return pool;
  80 }
  81
  82
  83 /* free all the resources of our pool */
  84 void
  85 pool_free(Pool *pool)
  86 {
  87   int i;
  88
  89   pool_freewhatprovides(pool);
  90   pool_freeidhashes(pool);
  91   pool_freeallrepos(pool, 1);
  92   solv_free(pool->id2arch);
  93   solv_free(pool->solvables);
  94   stringpool_free(&pool->ss);
  95   solv_free(pool->rels);
  96   pool_setvendorclasses(pool, 0);
  97   queue_free(&pool->vendormap);
  98   for (i = 0; i < POOL_TMPSPACEBUF; i++)
  99     solv_free(pool->tmpspace.buf[i]);
 100   for (i = 0; i < pool->nlanguages; i++)
 101     free((char *)pool->languages[i]);
 102   solv_free(pool->languages);
 103   solv_free(pool->languagecache);
 104   solv_free(pool);
 105 }
 106
 107 void
 108 pool_freeallrepos(Pool *pool, int reuseids)
 109 {
 110   int i;
 111
 112   pool_freewhatprovides(pool);
 113   for (i = 1; i < pool->nrepos; i++)
 114     if (pool->repos[i])
 115       repo_freedata(pool->repos[i]);
 116   pool->repos = solv_free(pool->repos);
 117   pool->nrepos = 0;
 118   pool->urepos = 0;
 119   /* the first two solvables don't belong to a repo */
 120   pool_free_solvable_block(pool, 2, pool->nsolvables - 2, reuseids);
 121 }
 122
 123 #ifdef MULTI_SEMANTICS
 124 void
 125 pool_setdisttype(Pool *pool, int disttype)
 126 {
 127   pool->disttype = disttype;
 128 }
 129 #endif
 130
 131 Id
 132 pool_add_solvable(Pool *pool)
 133 {
 134   pool->solvables = solv_extend(pool->solvables, pool->nsolvables, 1, sizeof(Solvable), SOLVABLE_BLOCK);
 135   memset(pool->solvables + pool->nsolvables, 0, sizeof(Solvable));
 136   return pool->nsolvables++;
 137 }
 138
 139 Id
 140 pool_add_solvable_block(Pool *pool, int count)
 141 {
 142   Id nsolvables = pool->nsolvables;
 143   if (!count)
 144     return nsolvables;
 145   pool->solvables = solv_extend(pool->solvables, pool->nsolvables, count, sizeof(Solvable), SOLVABLE_BLOCK);
 146   memset(pool->solvables + nsolvables, 0, sizeof(Solvable) * count);
 147   pool->nsolvables += count;
 148   return nsolvables;
 149 }
 150
 151 void
 152 pool_free_solvable_block(Pool *pool, Id start, int count, int reuseids)
 153 {
 154   if (!count)
 155     return;
 156   if (reuseids && start + count == pool->nsolvables)
 157     {
 158       /* might want to shrink solvable array */
 159       pool->nsolvables = start;
 160       return;
 161     }
 162   memset(pool->solvables + start, 0, sizeof(Solvable) * count);
 163 }
 164
 165
 166 void
 167 pool_set_installed(Pool *pool, Repo *installed)
 168 {
 169   if (pool->installed == installed)
 170     return;
 171   pool->installed = installed;
 172   pool_freewhatprovides(pool);
 173 }
 174
 175 static int
 176 pool_shrink_whatprovides_sortcmp(const void *ap, const void *bp, void *dp)
 177 {
 178   int r;
 179   Pool *pool = dp;
 180   Id oa, ob, *da, *db;
 181   oa = pool->whatprovides[*(Id *)ap];
 182   ob = pool->whatprovides[*(Id *)bp];
 183   if (oa == ob)
 184     return *(Id *)ap - *(Id *)bp;
 185   if (!oa)
 186     return -1;
 187   if (!ob)
 188     return 1;
 189   da = pool->whatprovidesdata + oa;
 190   db = pool->whatprovidesdata + ob;
 191   while (*db)
 192     if ((r = (*da++ - *db++)) != 0)
 193       return r;
 194   if (*da)
 195     return *da;
 196   return *(Id *)ap - *(Id *)bp;
 197 }
 198
 199 /*
 200  * pool_shrink_whatprovides  - unify whatprovides data
 201  *
 202  * whatprovides_rel must be empty for this to work!
 203  *
 204  */
 205 static void
 206 pool_shrink_whatprovides(Pool *pool)
 207 {
 208   Id i, id;
 209   Id *sorted;
 210   Id lastid, *last, *dp, *lp;
 211   Offset o;
 212   int r;
 213
 214   if (pool->ss.nstrings < 3)
 215     return;
 216   sorted = solv_malloc2(pool->ss.nstrings, sizeof(Id));
 217   for (id = 0; id < pool->ss.nstrings; id++)
 218     sorted[id] = id;
 219   solv_sort(sorted + 1, pool->ss.nstrings - 1, sizeof(Id), pool_shrink_whatprovides_sortcmp, pool);
 220   last = 0;
 221   lastid = 0;
 222   for (i = 1; i < pool->ss.nstrings; i++)
 223     {
 224       id = sorted[i];
 225       o = pool->whatprovides[id];
 226       if (o == 0 || o == 1)
 227         continue;
 228       dp = pool->whatprovidesdata + o;
 229       if (last)
 230         {
 231           lp = last;
 232           while (*dp)
 233             if (*dp++ != *lp++)
 234               {
 235                 last = 0;
 236                 break;
 237               }
 238           if (last && *lp)
 239             last = 0;
 240           if (last)
 241             {
 242               pool->whatprovides[id] = -lastid;
 243               continue;
 244             }
 245         }
 246       last = pool->whatprovidesdata + o;
 247       lastid = id;
 248     }
 249   solv_free(sorted);
 250   dp = pool->whatprovidesdata + 2;
 251   for (id = 1; id < pool->ss.nstrings; id++)
 252     {
 253       o = pool->whatprovides[id];
 254       if (o == 0 || o == 1)
 255         continue;
 256       if ((Id)o < 0)
 257         {
 258           i = -(Id)o;
 259           if (i >= id)
 260             abort();
 261           pool->whatprovides[id] = pool->whatprovides[i];
 262           continue;
 263         }
 264       lp = pool->whatprovidesdata + o;
 265       if (lp < dp)
 266         abort();
 267       pool->whatprovides[id] = dp - pool->whatprovidesdata;
 268       while ((*dp++ = *lp++) != 0)
 269         ;
 270     }
 271   o = dp - pool->whatprovidesdata;
 272   POOL_DEBUG(SOLV_DEBUG_STATS, "shrunk whatprovidesdata from %d to %d\n", pool->whatprovidesdataoff, o);
 273   if (pool->whatprovidesdataoff == o)
 274     return;
 275   r = pool->whatprovidesdataoff - o;
 276   pool->whatprovidesdataoff = o;
 277   pool->whatprovidesdata = solv_realloc(pool->whatprovidesdata, (o + pool->whatprovidesdataleft) * sizeof(Id));
 278   if (r > pool->whatprovidesdataleft)
 279     r = pool->whatprovidesdataleft;
 280   memset(pool->whatprovidesdata + o, 0, r * sizeof(Id));
 281 }
 282
 283
 284 /*
 285  * pool_createwhatprovides()
 286  *
 287  * create hashes over pool of solvables to ease provide lookups
 288  *
 289  */
 290 void
 291 pool_createwhatprovides(Pool *pool)
 292 {
 293   int i, num, np, extra;
 294   Offset off;
 295   Solvable *s;
 296   Id id;
 297   Offset *idp, n;
 298   Offset *whatprovides;
 299   Id *whatprovidesdata, *d;
 300   Repo *installed = pool->installed;
 301   unsigned int now;
 302
 303   now = solv_timems(0);
 304   POOL_DEBUG(SOLV_DEBUG_STATS, "number of solvables: %d\n", pool->nsolvables);
 305   POOL_DEBUG(SOLV_DEBUG_STATS, "number of ids: %d + %d\n", pool->ss.nstrings, pool->nrels);
 306
 307   pool_freeidhashes(pool);      /* XXX: should not be here! */
 308   pool_freewhatprovides(pool);
 309   num = pool->ss.nstrings;
 310   pool->whatprovides = whatprovides = solv_calloc_block(num, sizeof(Offset), WHATPROVIDES_BLOCK);
 311   pool->whatprovides_rel = solv_calloc_block(pool->nrels, sizeof(Offset), WHATPROVIDES_BLOCK);
 312
 313   /* count providers for each name */
 314   for (i = pool->nsolvables - 1; i > 0; i--)
 315     {
 316       Id *pp;
 317       s = pool->solvables + i;
 318       if (!s->provides || !s->repo || s->repo->disabled)
 319         continue;
 320       /* we always need the installed solvable in the whatprovides data,
 321          otherwise obsoletes/conflicts on them won't work */
 322       if (s->repo != installed && !pool_installable(pool, s))
 323         continue;
 324       pp = s->repo->idarraydata + s->provides;
 325       while ((id = *pp++) != 0)
 326         {
 327           while (ISRELDEP(id))
 328             {
 329               Reldep *rd = GETRELDEP(pool, id);
 330               id = rd->name;
 331             }
 332           whatprovides[id]++;          /* inc count of providers */
 333         }
 334     }
 335
 336   off = 2;      /* first entry is undef, second is empty list */
 337   np = 0;                              /* number of names provided */
 338   for (i = 0, idp = whatprovides; i < num; i++, idp++)
 339     {
 340       n = *idp;
 341       if (!n)                          /* no providers */
 342         continue;
 343       off += n;                        /* make space for all providers */
 344       *idp = off++;                    /* now idp points to terminating zero */
 345       np++;                            /* inc # of provider 'slots' for stats */
 346     }
 347
 348   POOL_DEBUG(SOLV_DEBUG_STATS, "provide ids: %d\n", np);
 349
 350   /* reserve some space for relation data */
 351   extra = 2 * pool->nrels;
 352   if (extra < 256)
 353     extra = 256;
 354
 355   POOL_DEBUG(SOLV_DEBUG_STATS, "provide space needed: %d + %d\n", off, extra);
 356
 357   /* alloc space for all providers + extra */
 358   whatprovidesdata = solv_calloc(off + extra, sizeof(Id));
 359
 360   /* now fill data for all provides */
 361   for (i = pool->nsolvables - 1; i > 0; i--)
 362     {
 363       Id *pp;
 364       s = pool->solvables + i;
 365       if (!s->provides || !s->repo || s->repo->disabled)
 366         continue;
 367       if (s->repo != installed && !pool_installable(pool, s))
 368         continue;
 369
 370       /* for all provides of this solvable */
 371       pp = s->repo->idarraydata + s->provides;
 372       while ((id = *pp++) != 0)
 373         {
 374           while (ISRELDEP(id))
 375             {
 376               Reldep *rd = GETRELDEP(pool, id);
 377               id = rd->name;
 378             }
 379           d = whatprovidesdata + whatprovides[id];   /* offset into whatprovidesdata */
 380           if (*d != i)          /* don't add same solvable twice */
 381             {
 382               d[-1] = i;
 383               whatprovides[id]--;
 384             }
 385         }
 386     }
 387   pool->whatprovidesdata = whatprovidesdata;
 388   pool->whatprovidesdataoff = off;
 389   pool->whatprovidesdataleft = extra;
 390   pool_shrink_whatprovides(pool);
 391   POOL_DEBUG(SOLV_DEBUG_STATS, "whatprovides memory used: %d K id array, %d K data\n", (pool->ss.nstrings + pool->nrels + WHATPROVIDES_BLOCK) / (int)(1024/sizeof(Id)), (pool->whatprovidesdataoff + pool->whatprovidesdataleft) / (int)(1024/sizeof(Id)));
 392   POOL_DEBUG(SOLV_DEBUG_STATS, "createwhatprovides took %d ms\n", solv_timems(now));
 393 }
 394
 395 /*
 396  * free all of our whatprovides data
 397  * be careful, everything internalized with pool_queuetowhatprovides is
 398  * gone, too
 399  */
 400 void
 401 pool_freewhatprovides(Pool *pool)
 402 {
 403   pool->whatprovides = solv_free(pool->whatprovides);
 404   pool->whatprovides_rel = solv_free(pool->whatprovides_rel);
 405   pool->whatprovidesdata = solv_free(pool->whatprovidesdata);
 406   pool->whatprovidesdataoff = 0;
 407   pool->whatprovidesdataleft = 0;
 408 }
 409
 410
 411 /******************************************************************************/
 412
 413 /*
 414  * pool_queuetowhatprovides  - add queue contents to whatprovidesdata
 415  *
 416  * on-demand filling of provider information
 417  * move queue data into whatprovidesdata
 418  * q: queue of Ids
 419  * returns: Offset into whatprovides
 420  *
 421  */
 422 Id
 423 pool_queuetowhatprovides(Pool *pool, Queue *q)
 424 {
 425   Offset off;
 426   int count = q->count;
 427
 428   if (count == 0)                      /* queue empty -> 1 */
 429     return 1;
 430
 431   /* extend whatprovidesdata if needed, +1 for ID_NULL-termination */
 432   if (pool->whatprovidesdataleft < count + 1)
 433     {
 434       POOL_DEBUG(SOLV_DEBUG_STATS, "growing provides hash data...\n");
 435       pool->whatprovidesdata = solv_realloc(pool->whatprovidesdata, (pool->whatprovidesdataoff + count + 4096) * sizeof(Id));
 436       pool->whatprovidesdataleft = count + 4096;
 437     }
 438
 439   /* copy queue to next free slot */
 440   off = pool->whatprovidesdataoff;
 441   memcpy(pool->whatprovidesdata + pool->whatprovidesdataoff, q->elements, count * sizeof(Id));
 442
 443   /* adapt count and ID_NULL-terminate */
 444   pool->whatprovidesdataoff += count;
 445   pool->whatprovidesdata[pool->whatprovidesdataoff++] = ID_NULL;
 446   pool->whatprovidesdataleft -= count + 1;
 447
 448   return (Id)off;
 449 }
 450
 451
 452 /*************************************************************************/
 453
 454 #if defined(MULTI_SEMANTICS)
 455 # define EVRCMP_DEPCMP (pool->disttype == DISTTYPE_DEB ? EVRCMP_COMPARE : EVRCMP_MATCH_RELEASE)
 456 #elif defined(DEBIAN_SEMANTICS)
 457 # define EVRCMP_DEPCMP EVRCMP_COMPARE
 458 #else
 459 # define EVRCMP_DEPCMP EVRCMP_MATCH_RELEASE
 460 #endif
 461
 462 /* check if a package's nevr matches a dependency */
 463
 464 int
 465 pool_match_nevr_rel(Pool *pool, Solvable *s, Id d)
 466 {
 467   Reldep *rd = GETRELDEP(pool, d);
 468   Id name = rd->name;
 469   Id evr = rd->evr;
 470   int flags = rd->flags;
 471
 472   if (flags > 7)
 473     {
 474       switch (flags)
 475         {
 476         case REL_ARCH:
 477           if (s->arch != evr)
 478             return 0;
 479           return pool_match_nevr(pool, s, name);
 480         case REL_OR:
 481           if (pool_match_nevr(pool, s, name))
 482             return 1;
 483           return pool_match_nevr(pool, s, evr);
 484         case REL_AND:
 485         case REL_WITH:
 486           if (!pool_match_nevr(pool, s, name))
 487             return 0;
 488           return pool_match_nevr(pool, s, evr);
 489         default:
 490           return 0;
 491         }
 492     }
 493   if (!pool_match_nevr(pool, s, name))
 494     return 0;
 495   if (evr == s->evr)
 496     return flags & 2 ? 1 : 0;
 497   if (!flags)
 498     return 0;
 499   if (flags == 7)
 500     return 1;
 501   if (flags != 2 && flags != 5)
 502     flags ^= 5;
 503   if ((flags & (1 << (1 + pool_evrcmp(pool, s->evr, evr, EVRCMP_DEPCMP)))) != 0)
 504     return 1;
 505   return 0;
 506 }
 507
 508 /* match (flags, evr) against provider (pflags, pevr) */
 509 static inline int
 510 pool_match_flags_evr(Pool *pool, int pflags, Id pevr, int flags, int evr)
 511 {
 512   if (!pflags || !flags || pflags >= 8 || flags >= 8)
 513     return 0;
 514   if (flags == 7 || pflags == 7)
 515     return 1;           /* rel provides every version */
 516   if ((pflags & flags & 5) != 0)
 517     return 1;           /* both rels show in the same direction */
 518   if (pevr == evr)
 519     {
 520       if ((pflags & flags & 2) != 0)
 521         return 1;       /* both have '=', match */
 522     }
 523   else
 524     {
 525       int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5);
 526       if ((f & (1 << (1 + pool_evrcmp(pool, pevr, evr, EVRCMP_DEPCMP)))) != 0)
 527         return 1;
 528     }
 529   return 0;
 530 }
 531
 532 /* match two dependencies (d1 = provider) */
 533
 534 int
 535 pool_match_dep(Pool *pool, Id d1, Id d2)
 536 {
 537   Reldep *rd1, *rd2;
 538
 539   if (d1 == d2)
 540     return 1;
 541   if (!ISRELDEP(d1))
 542     {
 543       if (!ISRELDEP(d2))
 544         return 0;
 545       rd2 = GETRELDEP(pool, d2);
 546       return pool_match_dep(pool, d1, rd2->name);
 547     }
 548   rd1 = GETRELDEP(pool, d1);
 549   if (!ISRELDEP(d2))
 550     {
 551       return pool_match_dep(pool, rd1->name, d2);
 552     }
 553   rd2 = GETRELDEP(pool, d2);
 554   /* first match name */
 555   if (!pool_match_dep(pool, rd1->name, rd2->name))
 556     return 0;
 557   /* name matches, check flags and evr */
 558   return pool_match_flags_evr(pool, rd1->flags, rd1->evr, rd2->flags, rd2->evr);
 559 }
 560
 561 /*
 562  * addrelproviders
 563  *
 564  * add packages fulfilling the relation to whatprovides array
 565  * no exact providers, do range match
 566  *
 567  */
 568
 569 Id
 570 pool_addrelproviders(Pool *pool, Id d)
 571 {
 572   Reldep *rd = GETRELDEP(pool, d);
 573   Reldep *prd;
 574   Queue plist;
 575   Id buf[16];
 576   Id name = rd->name;
 577   Id evr = rd->evr;
 578   int flags = rd->flags;
 579   Id pid, *pidp;
 580   Id p, *pp;
 581
 582   d = GETRELID(d);
 583   queue_init_buffer(&plist, buf, sizeof(buf)/sizeof(*buf));
 584
 585   if (flags >= 8)
 586     {
 587       /* special relation */
 588       Id wp = 0;
 589       Id *pp2, *pp3;
 590
 591       switch (flags)
 592         {
 593         case REL_AND:
 594         case REL_WITH:
 595           wp = pool_whatprovides(pool, name);
 596           pp2 = pool_whatprovides_ptr(pool, evr);
 597           pp = pool->whatprovidesdata + wp;
 598           while ((p = *pp++) != 0)
 599             {
 600               for (pp3 = pp2; *pp3; pp3++)
 601                 if (*pp3 == p)
 602                   break;
 603               if (*pp3)
 604                 queue_push(&plist, p);  /* found it */
 605               else
 606                 wp = 0;
 607             }
 608           break;
 609         case REL_OR:
 610           wp = pool_whatprovides(pool, name);
 611           pp = pool->whatprovidesdata + wp;
 612           if (!*pp)
 613             wp = pool_whatprovides(pool, evr);
 614           else
 615             {
 616               int cnt;
 617               while ((p = *pp++) != 0)
 618                 queue_push(&plist, p);
 619               cnt = plist.count;
 620               pp = pool_whatprovides_ptr(pool, evr);
 621               while ((p = *pp++) != 0)
 622                 queue_pushunique(&plist, p);
 623               if (plist.count != cnt)
 624                 wp = 0;
 625             }
 626           break;
 627         case REL_NAMESPACE:
 628           if (name == NAMESPACE_OTHERPROVIDERS)
 629             {
 630               wp = pool_whatprovides(pool, evr);
 631               break;
 632             }
 633           if (pool->nscallback)
 634             {
 635               /* ask callback which packages provide the dependency
 636                * 0:  none
 637                * 1:  the system (aka SYSTEMSOLVABLE)
 638                * >1: set of packages, stored as offset on whatprovidesdata
 639                */
 640               p = pool->nscallback(pool, pool->nscallbackdata, name, evr);
 641               if (p > 1)
 642                 wp = p;
 643               if (p == 1)
 644                 queue_push(&plist, SYSTEMSOLVABLE);
 645             }
 646           break;
 647         case REL_ARCH:
 648           /* small hack: make it possible to match <pkg>.src
 649            * we have to iterate over the solvables as src packages do not
 650            * provide anything, thus they are not indexed in our
 651            * whatprovides hash */
 652           if (evr == ARCH_SRC)
 653             {
 654               Solvable *s;
 655               for (p = 1, s = pool->solvables + p; p < pool->nsolvables; p++, s++)
 656                 {
 657                   if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC)
 658                     continue;
 659                   if (pool_match_nevr(pool, s, name))
 660                     queue_push(&plist, p);
 661                 }
 662               break;
 663             }
 664           wp = pool_whatprovides(pool, name);
 665           pp = pool->whatprovidesdata + wp;
 666           while ((p = *pp++) != 0)
 667             {
 668               Solvable *s = pool->solvables + p;
 669               if (s->arch == evr)
 670                 queue_push(&plist, p);
 671               else
 672                 wp = 0;
 673             }
 674           break;
 675         case REL_FILECONFLICT:
 676           pp = pool_whatprovides_ptr(pool, name);
 677           while ((p = *pp++) != 0)
 678             {
 679               Id origd = MAKERELDEP(d);
 680               Solvable *s = pool->solvables + p;
 681               if (!s->provides)
 682                 continue;
 683               pidp = s->repo->idarraydata + s->provides;
 684               while ((pid = *pidp++) != 0)
 685                 if (pid == origd)
 686                   break;
 687               if (pid)
 688                 queue_push(&plist, p);
 689             }
 690           break;
 691         default:
 692           break;
 693         }
 694       if (wp)
 695         {
 696           /* we can reuse an existing entry */
 697           queue_free(&plist);
 698           pool->whatprovides_rel[d] = wp;
 699           return wp;
 700         }
 701     }
 702   else if (flags)
 703     {
 704       /* simple version comparison relation */
 705 #if 0
 706       POOL_DEBUG(SOLV_DEBUG_STATS, "addrelproviders: what provides %s?\n", pool_dep2str(pool, name));
 707 #endif
 708       pp = pool_whatprovides_ptr(pool, name);
 709       while (ISRELDEP(name))
 710         {
 711           rd = GETRELDEP(pool, name);
 712           name = rd->name;
 713         }
 714       while ((p = *pp++) != 0)
 715         {
 716           Solvable *s = pool->solvables + p;
 717           if (!s->provides)
 718             {
 719               /* no provides - check nevr */
 720               if (pool_match_nevr_rel(pool, s, MAKERELDEP(d)))
 721                 queue_push(&plist, p);
 722               continue;
 723             }
 724           /* solvable p provides name in some rels */
 725           pidp = s->repo->idarraydata + s->provides;
 726           while ((pid = *pidp++) != 0)
 727             {
 728               if (pid == name)
 729                 {
 730 #if defined(MULTI_SEMANTICS)
 731                   if (pool->disttype == DISTTYPE_DEB)
 732                     continue;
 733                   else
 734                     break;
 735 #elif defined(DEBIAN_SEMANTICS)
 736                   continue;             /* unversioned provides can
 737                                          * never match versioned deps */
 738 #else
 739                   break;                /* yes, provides all versions */
 740 #endif
 741                 }
 742               if (!ISRELDEP(pid))
 743                 continue;               /* wrong provides name */
 744               prd = GETRELDEP(pool, pid);
 745               if (prd->name != name)
 746                 continue;               /* wrong provides name */
 747               /* right package, both deps are rels. check flags/evr */
 748               if (pool_match_flags_evr(pool, prd->flags, prd->evr, flags, evr))
 749                 break;  /* matches */
 750             }
 751           if (!pid)
 752             continue;   /* none of the providers matched */
 753           queue_push(&plist, p);
 754         }
 755       /* make our system solvable provide all unknown rpmlib() stuff */
 756       if (plist.count == 0 && !strncmp(pool_id2str(pool, name), "rpmlib(", 7))
 757         queue_push(&plist, SYSTEMSOLVABLE);
 758     }
 759   /* add providers to whatprovides */
 760 #if 0
 761   POOL_DEBUG(SOLV_DEBUG_STATS, "addrelproviders: adding %d packages to %d\n", plist.count, d);
 762 #endif
 763   pool->whatprovides_rel[d] = pool_queuetowhatprovides(pool, &plist);
 764   queue_free(&plist);
 765
 766   return pool->whatprovides_rel[d];
 767 }
 768
 769 /*************************************************************************/
 770
 771 void
 772 pool_debug(Pool *pool, int type, const char *format, ...)
 773 {
 774   va_list args;
 775   char buf[1024];
 776
 777   if ((type & (SOLV_FATAL|SOLV_ERROR)) == 0)
 778     {
 779       if ((pool->debugmask & type) == 0)
 780         return;
 781     }
 782   va_start(args, format);
 783   if (!pool->debugcallback)
 784     {
 785       if ((type & (SOLV_FATAL|SOLV_ERROR)) == 0 && !(pool->debugmask & SOLV_DEBUG_TO_STDERR))
 786         vprintf(format, args);
 787       else
 788         vfprintf(stderr, format, args);
 789       return;
 790     }
 791   vsnprintf(buf, sizeof(buf), format, args);
 792   pool->debugcallback(pool, pool->debugcallbackdata, type, buf);
 793 }
 794
 795 void
 796 pool_setdebuglevel(Pool *pool, int level)
 797 {
 798   int mask = SOLV_DEBUG_RESULT;
 799   if (level > 0)
 800     mask |= SOLV_DEBUG_STATS|SOLV_DEBUG_ANALYZE|SOLV_DEBUG_UNSOLVABLE|SOLV_DEBUG_SOLVER|SOLV_DEBUG_TRANSACTION;
 801   if (level > 1)
 802     mask |= SOLV_DEBUG_JOB|SOLV_DEBUG_SOLUTIONS|SOLV_DEBUG_POLICY;
 803   if (level > 2)
 804     mask |= SOLV_DEBUG_PROPAGATE;
 805   if (level > 3)
 806     mask |= SOLV_DEBUG_RULE_CREATION;
 807   mask |= pool->debugmask & SOLV_DEBUG_TO_STDERR;       /* keep bit */
 808   pool->debugmask = mask;
 809 }
 810
 811 void pool_setdebugcallback(Pool *pool, void (*debugcallback)(struct _Pool *, void *data, int type, const char *str), void *debugcallbackdata)
 812 {
 813   pool->debugcallback = debugcallback;
 814   pool->debugcallbackdata = debugcallbackdata;
 815 }
 816
 817 void pool_setdebugmask(Pool *pool, int mask)
 818 {
 819   pool->debugmask = mask;
 820 }
 821
 822 void pool_setloadcallback(Pool *pool, int (*cb)(struct _Pool *, struct _Repodata *, void *), void *loadcbdata)
 823 {
 824   pool->loadcallback = cb;
 825   pool->loadcallbackdata = loadcbdata;
 826 }
 827
 828 /*************************************************************************/
 829
 830 struct searchfiles {
 831   Id *ids;
 832   char **dirs;
 833   char **names;
 834   int nfiles;
 835   Map seen;
 836 };
 837
 838 #define SEARCHFILES_BLOCK 127
 839
 840 static void
 841 pool_addfileprovides_dep(Pool *pool, Id *ida, struct searchfiles *sf, struct searchfiles *isf)
 842 {
 843   Id dep, sid;
 844   const char *s, *sr;
 845   struct searchfiles *csf;
 846
 847   while ((dep = *ida++) != 0)
 848     {
 849       csf = sf;
 850       while (ISRELDEP(dep))
 851         {
 852           Reldep *rd;
 853           sid = pool->ss.nstrings + GETRELID(dep);
 854           if (MAPTST(&csf->seen, sid))
 855             {
 856               dep = 0;
 857               break;
 858             }
 859           MAPSET(&csf->seen, sid);
 860           rd = GETRELDEP(pool, dep);
 861           if (rd->flags < 8)
 862             dep = rd->name;
 863           else if (rd->flags == REL_NAMESPACE)
 864             {
 865               if (rd->name == NAMESPACE_INSTALLED || rd->name == NAMESPACE_SPLITPROVIDES)
 866                 {
 867                   csf = isf;
 868                   if (!csf || MAPTST(&csf->seen, sid))
 869                     {
 870                       dep = 0;
 871                       break;
 872                     }
 873                   MAPSET(&csf->seen, sid);
 874                 }
 875               dep = rd->evr;
 876             }
 877           else if (rd->flags == REL_FILECONFLICT)
 878             {
 879               dep = 0;
 880               break;
 881             }
 882           else
 883             {
 884               Id ids[2];
 885               ids[0] = rd->name;
 886               ids[1] = 0;
 887               pool_addfileprovides_dep(pool, ids, csf, isf);
 888               dep = rd->evr;
 889             }
 890         }
 891       if (!dep)
 892         continue;
 893       if (MAPTST(&csf->seen, dep))
 894         continue;
 895       MAPSET(&csf->seen, dep);
 896       s = pool_id2str(pool, dep);
 897       if (*s != '/')
 898         continue;
 899       csf->ids = solv_extend(csf->ids, csf->nfiles, 1, sizeof(Id), SEARCHFILES_BLOCK);
 900       csf->dirs = solv_extend(csf->dirs, csf->nfiles, 1, sizeof(const char *), SEARCHFILES_BLOCK);
 901       csf->names = solv_extend(csf->names, csf->nfiles, 1, sizeof(const char *), SEARCHFILES_BLOCK);
 902       csf->ids[csf->nfiles] = dep;
 903       sr = strrchr(s, '/');
 904       csf->names[csf->nfiles] = solv_strdup(sr + 1);
 905       csf->dirs[csf->nfiles] = solv_malloc(sr - s + 1);
 906       if (sr != s)
 907         strncpy(csf->dirs[csf->nfiles], s, sr - s);
 908       csf->dirs[csf->nfiles][sr - s] = 0;
 909       csf->nfiles++;
 910     }
 911 }
 912
 913 struct addfileprovides_cbdata {
 914   int nfiles;
 915   Id *ids;
 916   char **dirs;
 917   char **names;
 918
 919   Id *dids;
 920
 921   Map providedids;
 922
 923   Map useddirs;
 924 };
 925
 926 static int
 927 addfileprovides_cb(void *cbdata, Solvable *s, Repodata *data, Repokey *key, KeyValue *value)
 928 {
 929   struct addfileprovides_cbdata *cbd = cbdata;
 930   int i;
 931
 932   if (!cbd->useddirs.size)
 933     {
 934       map_init(&cbd->useddirs, data->dirpool.ndirs + 1);
 935       for (i = 0; i < cbd->nfiles; i++)
 936         {
 937           Id did;
 938           if (MAPTST(&cbd->providedids, cbd->ids[i]))
 939             {
 940               cbd->dids[i] = 0;
 941               continue;
 942             }
 943           did = repodata_str2dir(data, cbd->dirs[i], 0);
 944           cbd->dids[i] = did;
 945           if (did)
 946             MAPSET(&cbd->useddirs, did);
 947         }
 948     }
 949   if (value->id >= data->dirpool.ndirs || !MAPTST(&cbd->useddirs, value->id))
 950     return 0;
 951   for (i = 0; i < cbd->nfiles; i++)
 952     {
 953       if (cbd->dids[i] != value->id)
 954         continue;
 955       if (!strcmp(cbd->names[i], value->str))
 956         break;
 957     }
 958   if (i == cbd->nfiles)
 959     return 0;
 960   s->provides = repo_addid_dep(s->repo, s->provides, cbd->ids[i], SOLVABLE_FILEMARKER);
 961   return 0;
 962 }
 963
 964 static void
 965 pool_addfileprovides_search(Pool *pool, struct addfileprovides_cbdata *cbd, struct searchfiles *sf, Repo *repoonly)
 966 {
 967   Id p;
 968   Repodata *data;
 969   Repo *repo;
 970   Queue fileprovidesq;
 971   int i, j, repoid, repodataid;
 972   int provstart, provend;
 973   Map donemap;
 974   int ndone, incomplete;
 975
 976   if (!pool->urepos)
 977     return;
 978
 979   cbd->nfiles = sf->nfiles;
 980   cbd->ids = sf->ids;
 981   cbd->dirs = sf->dirs;
 982   cbd->names = sf->names;
 983   cbd->dids = solv_realloc2(cbd->dids, sf->nfiles, sizeof(Id));
 984   map_init(&cbd->providedids, pool->ss.nstrings);
 985
 986   repoid = 1;
 987   repo = repoonly ? repoonly : pool->repos[repoid];
 988   map_init(&donemap, pool->nsolvables);
 989   queue_init(&fileprovidesq);
 990   provstart = provend = 0;
 991   for (;;)
 992     {
 993       if (!repo || repo->disabled)
 994         {
 995           if (repoonly || ++repoid == pool->nrepos)
 996             break;
 997           repo = pool->repos[repoid];
 998           continue;
 999         }
1000       ndone = 0;
1001       FOR_REPODATAS(repo, repodataid, data)
1002         {
1003           if (ndone >= repo->nsolvables)
1004             break;
1005
1006           if (repodata_lookup_idarray(data, SOLVID_META, REPOSITORY_ADDEDFILEPROVIDES, &fileprovidesq))
1007             {
1008               map_empty(&cbd->providedids);
1009               for (i = 0; i < fileprovidesq.count; i++)
1010                 MAPSET(&cbd->providedids, fileprovidesq.elements[i]);
1011               provstart = data->start;
1012               provend = data->end;
1013               for (i = 0; i < cbd->nfiles; i++)
1014                 if (!MAPTST(&cbd->providedids, cbd->ids[i]))
1015                   break;
1016               if (i == cbd->nfiles)
1017                 {
1018                   /* great! no need to search files */
1019                   for (p = data->start; p < data->end; p++)
1020                     if (pool->solvables[p].repo == repo)
1021                       {
1022                         if (MAPTST(&donemap, p))
1023                           continue;
1024                         MAPSET(&donemap, p);
1025                         ndone++;
1026                       }
1027                   continue;
1028                 }
1029             }
1030
1031           if (!repodata_has_keyname(data, SOLVABLE_FILELIST))
1032             continue;
1033
1034           if (data->start < provstart || data->end > provend)
1035             {
1036               map_empty(&cbd->providedids);
1037               provstart = provend = 0;
1038             }
1039
1040           /* check if the data is incomplete */
1041           incomplete = 0;
1042           if (data->state == REPODATA_AVAILABLE)
1043             {
1044               for (j = 1; j < data->nkeys; j++)
1045                 if (data->keys[j].name != REPOSITORY_SOLVABLES && data->keys[j].name != SOLVABLE_FILELIST)
1046                   break;
1047               if (j < data->nkeys)
1048                 {
1049 #if 0
1050                   for (i = 0; i < cbd->nfiles; i++)
1051                     if (!MAPTST(&cbd->providedids, cbd->ids[i]) && !repodata_filelistfilter_matches(data, pool_id2str(pool, cbd->ids[i])))
1052                       printf("need complete filelist because of %s\n", pool_id2str(pool, cbd->ids[i]));
1053 #endif
1054                   for (i = 0; i < cbd->nfiles; i++)
1055                     if (!MAPTST(&cbd->providedids, cbd->ids[i]) && !repodata_filelistfilter_matches(data, pool_id2str(pool, cbd->ids[i])))
1056                       break;
1057                   if (i < cbd->nfiles)
1058                     incomplete = 1;
1059                 }
1060             }
1061
1062           /* do the search */
1063           map_init(&cbd->useddirs, 0);
1064           for (p = data->start; p < data->end; p++)
1065             if (pool->solvables[p].repo == repo)
1066               {
1067                 if (MAPTST(&donemap, p))
1068                   continue;
1069                 repodata_search(data, p, SOLVABLE_FILELIST, 0, addfileprovides_cb, cbd);
1070                 if (!incomplete)
1071                   {
1072                     MAPSET(&donemap, p);
1073                     ndone++;
1074                   }
1075               }
1076           map_free(&cbd->useddirs);
1077         }
1078
1079       if (repoonly || ++repoid == pool->nrepos)
1080         break;
1081       repo = pool->repos[repoid];
1082     }
1083   map_free(&donemap);
1084   queue_free(&fileprovidesq);
1085   map_free(&cbd->providedids);
1086 }
1087
1088 void
1089 pool_addfileprovides_queue(Pool *pool, Queue *idq)
1090 {
1091   Solvable *s;
1092   Repo *installed, *repo;
1093   struct searchfiles sf, isf, *isfp;
1094   struct addfileprovides_cbdata cbd;
1095   int i;
1096   unsigned int now;
1097
1098   installed = pool->installed;
1099   now = solv_timems(0);
1100   memset(&sf, 0, sizeof(sf));
1101   map_init(&sf.seen, pool->ss.nstrings + pool->nrels);
1102   memset(&isf, 0, sizeof(isf));
1103   map_init(&isf.seen, pool->ss.nstrings + pool->nrels);
1104
1105   if (idq)
1106     queue_empty(idq);
1107   isfp = installed ? &isf : 0;
1108   for (i = 1, s = pool->solvables + i; i < pool->nsolvables; i++, s++)
1109     {
1110       repo = s->repo;
1111       if (!repo)
1112         continue;
1113       if (s->obsoletes)
1114         pool_addfileprovides_dep(pool, repo->idarraydata + s->obsoletes, &sf, isfp);
1115       if (s->conflicts)
1116         pool_addfileprovides_dep(pool, repo->idarraydata + s->conflicts, &sf, isfp);
1117       if (s->requires)
1118         pool_addfileprovides_dep(pool, repo->idarraydata + s->requires, &sf, isfp);
1119       if (s->recommends)
1120         pool_addfileprovides_dep(pool, repo->idarraydata + s->recommends, &sf, isfp);
1121       if (s->suggests)
1122         pool_addfileprovides_dep(pool, repo->idarraydata + s->suggests, &sf, isfp);
1123       if (s->supplements)
1124         pool_addfileprovides_dep(pool, repo->idarraydata + s->supplements, &sf, isfp);
1125       if (s->enhances)
1126         pool_addfileprovides_dep(pool, repo->idarraydata + s->enhances, &sf, isfp);
1127     }
1128   map_free(&sf.seen);
1129   map_free(&isf.seen);
1130   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file dependencies, %d installed file dependencies\n", sf.nfiles, isf.nfiles);
1131   cbd.dids = 0;
1132   if (sf.nfiles)
1133     {
1134 #if 0
1135       for (i = 0; i < sf.nfiles; i++)
1136         POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in filelist\n", pool_id2str(pool, sf.ids[i]));
1137 #endif
1138       pool_addfileprovides_search(pool, &cbd, &sf, 0);
1139       if (idq)
1140         for (i = 0; i < sf.nfiles; i++)
1141           queue_push(idq, sf.ids[i]);
1142       solv_free(sf.ids);
1143       for (i = 0; i < sf.nfiles; i++)
1144         {
1145           solv_free(sf.dirs[i]);
1146           solv_free(sf.names[i]);
1147         }
1148       solv_free(sf.dirs);
1149       solv_free(sf.names);
1150     }
1151   if (isf.nfiles)
1152     {
1153 #if 0
1154       for (i = 0; i < isf.nfiles; i++)
1155         POOL_DEBUG(SOLV_DEBUG_STATS, "looking up %s in installed filelist\n", pool_id2str(pool, isf.ids[i]));
1156 #endif
1157       if (installed)
1158         pool_addfileprovides_search(pool, &cbd, &isf, installed);
1159       solv_free(isf.ids);
1160       for (i = 0; i < isf.nfiles; i++)
1161         {
1162           solv_free(isf.dirs[i]);
1163           solv_free(isf.names[i]);
1164         }
1165       solv_free(isf.dirs);
1166       solv_free(isf.names);
1167     }
1168   solv_free(cbd.dids);
1169   pool_freewhatprovides(pool);  /* as we have added provides */
1170   POOL_DEBUG(SOLV_DEBUG_STATS, "addfileprovides took %d ms\n", solv_timems(now));
1171 }
1172
1173 void
1174 pool_addfileprovides(Pool *pool)
1175 {
1176   pool_addfileprovides_queue(pool, 0);
1177 }
1178
1179 void
1180 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)
1181 {
1182   if (p)
1183     {
1184       if (pool->solvables[p].repo)
1185         repo_search(pool->solvables[p].repo, p, key, match, flags, callback, cbdata);
1186       return;
1187     }
1188   /* FIXME: obey callback return value! */
1189   for (p = 1; p < pool->nsolvables; p++)
1190     if (pool->solvables[p].repo)
1191       repo_search(pool->solvables[p].repo, p, key, match, flags, callback, cbdata);
1192 }
1193
1194 void
1195 pool_clear_pos(Pool *pool)
1196 {
1197   memset(&pool->pos, 0, sizeof(pool->pos));
1198 }
1199
1200
1201 void
1202 pool_set_languages(Pool *pool, const char **languages, int nlanguages)
1203 {
1204   int i;
1205
1206   pool->languagecache = solv_free(pool->languagecache);
1207   pool->languagecacheother = 0;
1208   if (pool->nlanguages)
1209     {
1210       for (i = 0; i < pool->nlanguages; i++)
1211         free((char *)pool->languages[i]);
1212       free(pool->languages);
1213     }
1214   pool->nlanguages = nlanguages;
1215   if (!nlanguages)
1216     return;
1217   pool->languages = solv_calloc(nlanguages, sizeof(const char **));
1218   for (i = 0; i < pool->nlanguages; i++)
1219     pool->languages[i] = solv_strdup(languages[i]);
1220 }
1221
1222 Id
1223 pool_id2langid(Pool *pool, Id id, const char *lang, int create)
1224 {
1225   const char *n;
1226   char buf[256], *p;
1227   int l;
1228
1229   if (!lang || !*lang)
1230     return id;
1231   n = pool_id2str(pool, id);
1232   l = strlen(n) + strlen(lang) + 2;
1233   if (l > sizeof(buf))
1234     p = solv_malloc(strlen(n) + strlen(lang) + 2);
1235   else
1236     p = buf;
1237   sprintf(p, "%s:%s", n, lang);
1238   id = pool_str2id(pool, p, create);
1239   if (p != buf)
1240     free(p);
1241   return id;
1242 }
1243
1244 char *
1245 pool_alloctmpspace(Pool *pool, int len)
1246 {
1247   int n = pool->tmpspace.n;
1248   if (!len)
1249     return 0;
1250   if (len > pool->tmpspace.len[n])
1251     {
1252       pool->tmpspace.buf[n] = solv_realloc(pool->tmpspace.buf[n], len + 32);
1253       pool->tmpspace.len[n] = len + 32;
1254     }
1255   pool->tmpspace.n = (n + 1) % POOL_TMPSPACEBUF;
1256   return pool->tmpspace.buf[n];
1257 }
1258
1259 static char *
1260 pool_alloctmpspace_free(Pool *pool, const char *space, int len)
1261 {
1262   if (space)
1263     {
1264       int n, oldn;
1265       n = oldn = pool->tmpspace.n;
1266       for (;;)
1267         {
1268           if (!n--)
1269             n = POOL_TMPSPACEBUF - 1;
1270           if (n == oldn)
1271             break;
1272           if (pool->tmpspace.buf[n] != space)
1273             continue;
1274           if (len > pool->tmpspace.len[n])
1275             {
1276               pool->tmpspace.buf[n] = solv_realloc(pool->tmpspace.buf[n], len + 32);
1277               pool->tmpspace.len[n] = len + 32;
1278             }
1279           return pool->tmpspace.buf[n];
1280         }
1281     }
1282   return 0;
1283 }
1284
1285 void
1286 pool_freetmpspace(Pool *pool, const char *space)
1287 {
1288   int n = pool->tmpspace.n;
1289   if (!space)
1290     return;
1291   n = (n + (POOL_TMPSPACEBUF - 1)) % POOL_TMPSPACEBUF;
1292   if (pool->tmpspace.buf[n] == space)
1293     pool->tmpspace.n = n;
1294 }
1295
1296 char *
1297 pool_tmpjoin(Pool *pool, const char *str1, const char *str2, const char *str3)
1298 {
1299   int l1, l2, l3;
1300   char *s, *str;
1301   l1 = str1 ? strlen(str1) : 0;
1302   l2 = str2 ? strlen(str2) : 0;
1303   l3 = str3 ? strlen(str3) : 0;
1304   s = str = pool_alloctmpspace(pool, l1 + l2 + l3 + 1);
1305   if (l1)
1306     {
1307       strcpy(s, str1);
1308       s += l1;
1309     }
1310   if (l2)
1311     {
1312       strcpy(s, str2);
1313       s += l2;
1314     }
1315   if (l3)
1316     {
1317       strcpy(s, str3);
1318       s += l3;
1319     }
1320   *s = 0;
1321   return str;
1322 }
1323
1324 char *
1325 pool_tmpappend(Pool *pool, const char *str1, const char *str2, const char *str3)
1326 {
1327   int l1, l2, l3;
1328   char *s, *str;
1329
1330   l1 = str1 ? strlen(str1) : 0;
1331   l2 = str2 ? strlen(str2) : 0;
1332   l3 = str3 ? strlen(str3) : 0;
1333   str = pool_alloctmpspace_free(pool, str1, l1 + l2 + l3 + 1);
1334   if (str)
1335     str1 = str;
1336   else
1337     str = pool_alloctmpspace(pool, l1 + l2 + l3 + 1);
1338   s = str;
1339   if (l1)
1340     {
1341       if (s != str1)
1342         strcpy(s, str1);
1343       s += l1;
1344     }
1345   if (l2)
1346     {
1347       strcpy(s, str2);
1348       s += l2;
1349     }
1350   if (l3)
1351     {
1352       strcpy(s, str3);
1353       s += l3;
1354     }
1355   *s = 0;
1356   return str;
1357 }
1358
1359 const char *
1360 pool_bin2hex(Pool *pool, const unsigned char *buf, int len)
1361 {
1362   char *s;
1363   if (!len)
1364     return "";
1365   s = pool_alloctmpspace(pool, 2 * len + 1);
1366   solv_bin2hex(buf, len, s);
1367   return s;
1368 }
1369
1370 /*******************************************************************/
1371
1372 struct mptree {
1373   Id sibling;
1374   Id child;
1375   const char *comp;
1376   int compl;
1377   Id mountpoint;
1378 };
1379
1380 struct ducbdata {
1381   DUChanges *mps;
1382   struct mptree *mptree;
1383   int addsub;
1384   int hasdu;
1385
1386   Id *dirmap;
1387   int nmap;
1388   Repodata *olddata;
1389 };
1390
1391
1392 static int
1393 solver_fill_DU_cb(void *cbdata, Solvable *s, Repodata *data, Repokey *key, KeyValue *value)
1394 {
1395   struct ducbdata *cbd = cbdata;
1396   Id mp;
1397
1398   if (data != cbd->olddata)
1399     {
1400       Id dn, mp, comp, *dirmap, *dirs;
1401       int i, compl;
1402       const char *compstr;
1403       struct mptree *mptree;
1404
1405       /* create map from dir to mptree */
1406       cbd->dirmap = solv_free(cbd->dirmap);
1407       cbd->nmap = 0;
1408       dirmap = solv_calloc(data->dirpool.ndirs, sizeof(Id));
1409       mptree = cbd->mptree;
1410       mp = 0;
1411       for (dn = 2, dirs = data->dirpool.dirs + dn; dn < data->dirpool.ndirs; dn++)
1412         {
1413           comp = *dirs++;
1414           if (comp <= 0)
1415             {
1416               mp = dirmap[-comp];
1417               continue;
1418             }
1419           if (mp < 0)
1420             {
1421               /* unconnected */
1422               dirmap[dn] = mp;
1423               continue;
1424             }
1425           if (!mptree[mp].child)
1426             {
1427               dirmap[dn] = -mp;
1428               continue;
1429             }
1430           if (data->localpool)
1431             compstr = stringpool_id2str(&data->spool, comp);
1432           else
1433             compstr = pool_id2str(data->repo->pool, comp);
1434           compl = strlen(compstr);
1435           for (i = mptree[mp].child; i; i = mptree[i].sibling)
1436             if (mptree[i].compl == compl && !strncmp(mptree[i].comp, compstr, compl))
1437               break;
1438           dirmap[dn] = i ? i : -mp;
1439         }
1440       /* change dirmap to point to mountpoint instead of mptree */
1441       for (dn = 0; dn < data->dirpool.ndirs; dn++)
1442         {
1443           mp = dirmap[dn];
1444           dirmap[dn] = mptree[mp > 0 ? mp : -mp].mountpoint;
1445         }
1446       cbd->dirmap = dirmap;
1447       cbd->nmap = data->dirpool.ndirs;
1448       cbd->olddata = data;
1449     }
1450   cbd->hasdu = 1;
1451   if (value->id < 0 || value->id >= cbd->nmap)
1452     return 0;
1453   mp = cbd->dirmap[value->id];
1454   if (mp < 0)
1455     return 0;
1456   if (cbd->addsub > 0)
1457     {
1458       cbd->mps[mp].kbytes += value->num;
1459       cbd->mps[mp].files += value->num2;
1460     }
1461   else
1462     {
1463       cbd->mps[mp].kbytes -= value->num;
1464       cbd->mps[mp].files -= value->num2;
1465     }
1466   return 0;
1467 }
1468
1469 static void
1470 propagate_mountpoints(struct mptree *mptree, int pos, Id mountpoint)
1471 {
1472   int i;
1473   if (mptree[pos].mountpoint == -1)
1474     mptree[pos].mountpoint = mountpoint;
1475   else
1476     mountpoint = mptree[pos].mountpoint;
1477   for (i = mptree[pos].child; i; i = mptree[i].sibling)
1478     propagate_mountpoints(mptree, i, mountpoint);
1479 }
1480
1481 #define MPTREE_BLOCK 15
1482
1483 void
1484 pool_calc_duchanges(Pool *pool, Map *installedmap, DUChanges *mps, int nmps)
1485 {
1486   char *p;
1487   const char *path, *compstr;
1488   struct mptree *mptree;
1489   int i, nmptree;
1490   int pos, compl;
1491   int mp;
1492   struct ducbdata cbd;
1493   Solvable *s;
1494   Id sp;
1495   Map ignoredu;
1496   Repo *oldinstalled = pool->installed;
1497
1498   memset(&ignoredu, 0, sizeof(ignoredu));
1499   cbd.mps = mps;
1500   cbd.addsub = 0;
1501   cbd.dirmap = 0;
1502   cbd.nmap = 0;
1503   cbd.olddata = 0;
1504
1505   mptree = solv_extend_resize(0, 1, sizeof(struct mptree), MPTREE_BLOCK);
1506
1507   /* our root node */
1508   mptree[0].sibling = 0;
1509   mptree[0].child = 0;
1510   mptree[0].comp = 0;
1511   mptree[0].compl = 0;
1512   mptree[0].mountpoint = -1;
1513   nmptree = 1;
1514
1515   /* create component tree */
1516   for (mp = 0; mp < nmps; mp++)
1517     {
1518       mps[mp].kbytes = 0;
1519       mps[mp].files = 0;
1520       pos = 0;
1521       path = mps[mp].path;
1522       while(*path == '/')
1523         path++;
1524       while (*path)
1525         {
1526           if ((p = strchr(path, '/')) == 0)
1527             {
1528               compstr = path;
1529               compl = strlen(compstr);
1530               path += compl;
1531             }
1532           else
1533             {
1534               compstr = path;
1535               compl = p - path;
1536               path = p + 1;
1537               while(*path == '/')
1538                 path++;
1539             }
1540           for (i = mptree[pos].child; i; i = mptree[i].sibling)
1541             if (mptree[i].compl == compl && !strncmp(mptree[i].comp, compstr, compl))
1542               break;
1543           if (!i)
1544             {
1545               /* create new node */
1546               mptree = solv_extend(mptree, nmptree, 1, sizeof(struct mptree), MPTREE_BLOCK);
1547               i = nmptree++;
1548               mptree[i].sibling = mptree[pos].child;
1549               mptree[i].child = 0;
1550               mptree[i].comp = compstr;
1551               mptree[i].compl = compl;
1552               mptree[i].mountpoint = -1;
1553               mptree[pos].child = i;
1554             }
1555           pos = i;
1556         }
1557       mptree[pos].mountpoint = mp;
1558     }
1559
1560   propagate_mountpoints(mptree, 0, mptree[0].mountpoint);
1561
1562 #if 0
1563   for (i = 0; i < nmptree; i++)
1564     {
1565       printf("#%d sibling: %d\n", i, mptree[i].sibling);
1566       printf("#%d child: %d\n", i, mptree[i].child);
1567       printf("#%d comp: %s\n", i, mptree[i].comp);
1568       printf("#%d compl: %d\n", i, mptree[i].compl);
1569       printf("#%d mountpont: %d\n", i, mptree[i].mountpoint);
1570     }
1571 #endif
1572
1573   cbd.mptree = mptree;
1574   cbd.addsub = 1;
1575   for (sp = 1, s = pool->solvables + sp; sp < pool->nsolvables; sp++, s++)
1576     {
1577       if (!s->repo || (oldinstalled && s->repo == oldinstalled))
1578         continue;
1579       if (!MAPTST(installedmap, sp))
1580         continue;
1581       cbd.hasdu = 0;
1582       repo_search(s->repo, sp, SOLVABLE_DISKUSAGE, 0, 0, solver_fill_DU_cb, &cbd);
1583       if (!cbd.hasdu && oldinstalled)
1584         {
1585           Id op, opp;
1586           /* no du data available, ignore data of all installed solvables we obsolete */
1587           if (!ignoredu.map)
1588             map_init(&ignoredu, oldinstalled->end - oldinstalled->start);
1589           if (s->obsoletes)
1590             {
1591               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
1592               while ((obs = *obsp++) != 0)
1593                 FOR_PROVIDES(op, opp, obs)
1594                   if (op >= oldinstalled->start && op < oldinstalled->end)
1595                     MAPSET(&ignoredu, op - oldinstalled->start);
1596             }
1597           FOR_PROVIDES(op, opp, s->name)
1598             if (pool->solvables[op].name == s->name)
1599               if (op >= oldinstalled->start && op < oldinstalled->end)
1600                 MAPSET(&ignoredu, op - oldinstalled->start);
1601         }
1602     }
1603   cbd.addsub = -1;
1604   if (oldinstalled)
1605     {
1606       /* assumes we allways have du data for installed solvables */
1607       FOR_REPO_SOLVABLES(oldinstalled, sp, s)
1608         {
1609           if (MAPTST(installedmap, sp))
1610             continue;
1611           if (ignoredu.map && MAPTST(&ignoredu, sp - oldinstalled->start))
1612             continue;
1613           repo_search(oldinstalled, sp, SOLVABLE_DISKUSAGE, 0, 0, solver_fill_DU_cb, &cbd);
1614         }
1615     }
1616   if (ignoredu.map)
1617     map_free(&ignoredu);
1618   solv_free(cbd.dirmap);
1619   solv_free(mptree);
1620 }
1621
1622 int
1623 pool_calc_installsizechange(Pool *pool, Map *installedmap)
1624 {
1625   Id sp;
1626   Solvable *s;
1627   int change = 0;
1628   Repo *oldinstalled = pool->installed;
1629
1630   for (sp = 1, s = pool->solvables + sp; sp < pool->nsolvables; sp++, s++)
1631     {
1632       if (!s->repo || (oldinstalled && s->repo == oldinstalled))
1633         continue;
1634       if (!MAPTST(installedmap, sp))
1635         continue;
1636       change += solvable_lookup_num(s, SOLVABLE_INSTALLSIZE, 0);
1637     }
1638   if (oldinstalled)
1639     {
1640       FOR_REPO_SOLVABLES(oldinstalled, sp, s)
1641         {
1642           if (MAPTST(installedmap, sp))
1643             continue;
1644           change -= solvable_lookup_num(s, SOLVABLE_INSTALLSIZE, 0);
1645         }
1646     }
1647   return change;
1648 }
1649
1650 /* map:
1651  *  1: installed
1652  *  2: conflicts with installed
1653  *  8: interesting (only true if installed)
1654  * 16: undecided
1655  */
1656
1657 static inline Id dep2name(Pool *pool, Id dep)
1658 {
1659   while (ISRELDEP(dep))
1660     {
1661       Reldep *rd = rd = GETRELDEP(pool, dep);
1662       dep = rd->name;
1663     }
1664   return dep;
1665 }
1666
1667 static int providedbyinstalled_multiversion(Pool *pool, unsigned char *map, Id n, Id con)
1668 {
1669   Id p, pp;
1670   Solvable *sn = pool->solvables + n;
1671
1672   FOR_PROVIDES(p, pp, sn->name)
1673     {
1674       Solvable *s = pool->solvables + p;
1675       if (s->name != sn->name || s->arch != sn->arch)
1676         continue;
1677       if ((map[p] & 9) != 9)
1678         continue;
1679       if (pool_match_nevr(pool, pool->solvables + p, con))
1680         continue;
1681       return 1;         /* found installed package that doesn't conflict */
1682     }
1683   return 0;
1684 }
1685
1686 static inline int providedbyinstalled(Pool *pool, unsigned char *map, Id dep, int ispatch, Map *noobsoletesmap)
1687 {
1688   Id p, pp;
1689   int r = 0;
1690   FOR_PROVIDES(p, pp, dep)
1691     {
1692       if (p == SYSTEMSOLVABLE)
1693         return 1;       /* always boring, as never constraining */
1694       if (ispatch && !pool_match_nevr(pool, pool->solvables + p, dep))
1695         continue;
1696       if (ispatch && noobsoletesmap && noobsoletesmap->size && MAPTST(noobsoletesmap, p) && ISRELDEP(dep))
1697         if (providedbyinstalled_multiversion(pool, map, p, dep))
1698           continue;
1699       if ((map[p] & 9) == 9)
1700         return 9;
1701       r |= map[p] & 17;
1702     }
1703   return r;
1704 }
1705
1706 /*
1707  * pool_trivial_installable - calculate if a set of solvables is
1708  * trivial installable without any other installs/deinstalls of
1709  * packages not belonging to the set.
1710  *
1711  * the state is returned in the result queue:
1712  * 1:  solvable is installable without any other package changes
1713  * 0:  solvable is not installable
1714  * -1: solvable is installable, but doesn't constrain any installed packages
1715  */
1716
1717 void
1718 pool_trivial_installable_noobsoletesmap(Pool *pool, Map *installedmap, Queue *pkgs, Queue *res, Map *noobsoletesmap)
1719 {
1720   int i, r, m, did;
1721   Id p, *dp, con, *conp, req, *reqp;
1722   unsigned char *map;
1723   Solvable *s;
1724
1725   map = solv_calloc(pool->nsolvables, 1);
1726   for (p = 1; p < pool->nsolvables; p++)
1727     {
1728       if (!MAPTST(installedmap, p))
1729         continue;
1730       map[p] |= 9;
1731       s = pool->solvables + p;
1732       if (!s->conflicts)
1733         continue;
1734       conp = s->repo->idarraydata + s->conflicts;
1735       while ((con = *conp++) != 0)
1736         {
1737           dp = pool_whatprovides_ptr(pool, con);
1738           for (; *dp; dp++)
1739             map[p] |= 2;        /* XXX: self conflict ? */
1740         }
1741     }
1742   for (i = 0; i < pkgs->count; i++)
1743     map[pkgs->elements[i]] = 16;
1744
1745   for (i = 0, did = 0; did < pkgs->count; i++, did++)
1746     {
1747       if (i == pkgs->count)
1748         i = 0;
1749       p = pkgs->elements[i];
1750       if ((map[p] & 16) == 0)
1751         continue;
1752       if ((map[p] & 2) != 0)
1753         {
1754           map[p] = 2;
1755           continue;
1756         }
1757       s = pool->solvables + p;
1758       m = 1;
1759       if (s->requires)
1760         {
1761           reqp = s->repo->idarraydata + s->requires;
1762           while ((req = *reqp++) != 0)
1763             {
1764               if (req == SOLVABLE_PREREQMARKER)
1765                 continue;
1766               r = providedbyinstalled(pool, map, req, 0, 0);
1767               if (!r)
1768                 {
1769                   /* decided and miss */
1770                   map[p] = 2;
1771                   break;
1772                 }
1773               m |= r;   /* 1 | 9 | 16 | 17 */
1774             }
1775           if (req)
1776             continue;
1777           if ((m & 9) == 9)
1778             m = 9;
1779         }
1780       if (s->conflicts)
1781         {
1782           int ispatch = 0;      /* see solver.c patch handling */
1783
1784           if (!strncmp("patch:", pool_id2str(pool, s->name), 6))
1785             ispatch = 1;
1786           conp = s->repo->idarraydata + s->conflicts;
1787           while ((con = *conp++) != 0)
1788             {
1789               if ((providedbyinstalled(pool, map, con, ispatch, noobsoletesmap) & 1) != 0)
1790                 {
1791                   map[p] = 2;
1792                   break;
1793                 }
1794               if ((m == 1 || m == 17) && ISRELDEP(con))
1795                 {
1796                   con = dep2name(pool, con);
1797                   if ((providedbyinstalled(pool, map, con, ispatch, noobsoletesmap) & 1) != 0)
1798                     m = 9;
1799                 }
1800             }
1801           if (con)
1802             continue;   /* found a conflict */
1803         }
1804 #if 0
1805       if (s->repo && s->repo != oldinstalled)
1806         {
1807           Id p2, obs, *obsp, *pp;
1808           Solvable *s2;
1809           if (s->obsoletes)
1810             {
1811               obsp = s->repo->idarraydata + s->obsoletes;
1812               while ((obs = *obsp++) != 0)
1813                 {
1814                   if ((providedbyinstalled(pool, map, obs, 0, 0) & 1) != 0)
1815                     {
1816                       map[p] = 2;
1817                       break;
1818                     }
1819                 }
1820               if (obs)
1821                 continue;
1822             }
1823           FOR_PROVIDES(p2, pp, s->name)
1824             {
1825               s2 = pool->solvables + p2;
1826               if (s2->name == s->name && (map[p2] & 1) != 0)
1827                 {
1828                   map[p] = 2;
1829                   break;
1830                 }
1831             }
1832           if (p2)
1833             continue;
1834         }
1835 #endif
1836       if (m != map[p])
1837         {
1838           map[p] = m;
1839           did = 0;
1840         }
1841     }
1842   queue_free(res);
1843   queue_init_clone(res, pkgs);
1844   for (i = 0; i < pkgs->count; i++)
1845     {
1846       m = map[pkgs->elements[i]];
1847       if ((m & 9) == 9)
1848         r = 1;
1849       else if (m & 1)
1850         r = -1;
1851       else
1852         r = 0;
1853       res->elements[i] = r;
1854     }
1855   free(map);
1856 }
1857
1858 void
1859 pool_trivial_installable(Pool *pool, Map *installedmap, Queue *pkgs, Queue *res)
1860 {
1861   pool_trivial_installable_noobsoletesmap(pool, installedmap, pkgs, res, 0);
1862 }
1863
1864 const char *
1865 pool_lookup_str(Pool *pool, Id entry, Id keyname)
1866 {
1867   if (entry == SOLVID_POS && pool->pos.repo)
1868     return repodata_lookup_str(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname);
1869   if (entry <= 0)
1870     return 0;
1871   return solvable_lookup_str(pool->solvables + entry, keyname);
1872 }
1873
1874 Id
1875 pool_lookup_id(Pool *pool, Id entry, Id keyname)
1876 {
1877   if (entry == SOLVID_POS && pool->pos.repo)
1878     {
1879       Repodata *data = pool->pos.repo->repodata + pool->pos.repodataid;
1880       Id id = repodata_lookup_id(data, SOLVID_POS, keyname);
1881       return data->localpool ? repodata_globalize_id(data, id, 1) : id;
1882     }
1883   if (entry <= 0)
1884     return 0;
1885   return solvable_lookup_id(pool->solvables + entry, keyname);
1886 }
1887
1888 unsigned int
1889 pool_lookup_num(Pool *pool, Id entry, Id keyname, unsigned int notfound)
1890 {
1891   if (entry == SOLVID_POS && pool->pos.repo)
1892     {
1893       unsigned int value;
1894       if (repodata_lookup_num(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname, &value))
1895         return value;
1896       return notfound;
1897     }
1898   if (entry <= 0)
1899     return notfound;
1900   return solvable_lookup_num(pool->solvables + entry, keyname, notfound);
1901 }
1902
1903 int
1904 pool_lookup_void(Pool *pool, Id entry, Id keyname)
1905 {
1906   if (entry == SOLVID_POS && pool->pos.repo)
1907     return repodata_lookup_void(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname);
1908   if (entry <= 0)
1909     return 0;
1910   return solvable_lookup_void(pool->solvables + entry, keyname);
1911 }
1912
1913 const unsigned char *
1914 pool_lookup_bin_checksum(Pool *pool, Id entry, Id keyname, Id *typep)
1915 {
1916   if (entry == SOLVID_POS && pool->pos.repo)
1917     return repodata_lookup_bin_checksum(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname, typep);
1918   if (entry <= 0)
1919     return 0;
1920   return solvable_lookup_bin_checksum(pool->solvables + entry, keyname, typep);
1921 }
1922
1923 const char *
1924 pool_lookup_checksum(Pool *pool, Id entry, Id keyname, Id *typep)
1925 {
1926   if (entry == SOLVID_POS && pool->pos.repo)
1927     {
1928       const unsigned char *chk = repodata_lookup_bin_checksum(pool->pos.repo->repodata + pool->pos.repodataid, SOLVID_POS, keyname, typep);
1929       return chk ? repodata_chk2str(pool->pos.repo->repodata + pool->pos.repodataid, *typep, chk) : 0;
1930     }
1931   if (entry <= 0)
1932     return 0;
1933   return solvable_lookup_checksum(pool->solvables + entry, keyname, typep);
1934 }
1935
1936 void
1937 pool_add_fileconflicts_deps(Pool *pool, Queue *conflicts)
1938 {
1939   int hadhashes = pool->relhashtbl ? 1 : 0;
1940   Solvable *s;
1941   Id fn, p, q, md5;
1942   Id id;
1943   int i;
1944
1945   if (!conflicts->count)
1946     return;
1947   pool_freewhatprovides(pool);
1948   for (i = 0; i < conflicts->count; i += 5)
1949     {
1950       fn = conflicts->elements[i];
1951       p = conflicts->elements[i + 1];
1952       md5 = conflicts->elements[i + 2];
1953       q = conflicts->elements[i + 3];
1954       id = pool_rel2id(pool, fn, md5, REL_FILECONFLICT, 1);
1955       s = pool->solvables + p;
1956       if (!s->repo)
1957         continue;
1958       s->provides = repo_addid_dep(s->repo, s->provides, id, SOLVABLE_FILEMARKER);
1959       s = pool->solvables + q;
1960       if (!s->repo)
1961         continue;
1962       s->conflicts = repo_addid_dep(s->repo, s->conflicts, id, 0);
1963     }
1964   if (!hadhashes)
1965     pool_freeidhashes(pool);
1966 }
1967
1968 /* EOF */