lib/rpmal.c

   1 /** \ingroup rpmdep
   2  * \file lib/rpmal.c
   3  */
   4
   5 #include "system.h"
   6
   7 #include <rpmlib.h>
   8
   9 #include <rpmal.h>
  10 #include <rpmds.h>
  11 #include <rpmfi.h>
  12
  13 #include "debug.h"
  14
  15 typedef struct availablePackage_s * availablePackage;
  16
  17 int _rpmal_debug = 0;
  18
  19
  20 /** \ingroup rpmdep
  21  * Info about a single package to be installed.
  22  */
  23 struct availablePackage_s {
  24     rpmds provides;             /*!< Provides: dependencies. */
  25     rpmfi fi;                   /*!< File info set. */
  26
  27     uint32_t tscolor;           /*!< Transaction color bits. */
  28
  29     fnpyKey key;                /*!< Associated file name/python object */
  30
  31 };
  32
  33 typedef struct availableIndexEntry_s *  availableIndexEntry;
  34
  35 /** \ingroup rpmdep
  36  * A single available item (e.g. a Provides: dependency).
  37  */
  38 struct availableIndexEntry_s {
  39     rpmalKey pkgKey;            /*!< Containing package. */
  40     const char * entry;         /*!< Dependency name. */
  41     unsigned short entryLen;    /*!< No. of bytes in name. */
  42     unsigned short entryIx;     /*!< Dependency index. */
  43     enum indexEntryType {
  44         IET_PROVIDES=1                  /*!< A Provides: dependency. */
  45     } type;                     /*!< Type of available item. */
  46 };
  47
  48 typedef struct availableIndex_s *       availableIndex;
  49
  50 /** \ingroup rpmdep
  51  * Index of all available items.
  52  */
  53 struct availableIndex_s {
  54     availableIndexEntry index;  /*!< Array of available items. */
  55     int size;                   /*!< No. of available items. */
  56     int k;                      /*!< Current index. */
  57 };
  58
  59 typedef struct fileIndexEntry_s *       fileIndexEntry;
  60
  61 /** \ingroup rpmdep
  62  * A file to be installed/removed.
  63  */
  64 struct fileIndexEntry_s {
  65     const char * baseName;      /*!< File basename. */
  66     int baseNameLen;
  67     rpmalNum pkgNum;            /*!< Containing package index. */
  68     uint32_t ficolor;
  69 };
  70
  71 typedef struct dirInfo_s *              dirInfo;
  72
  73 /** \ingroup rpmdep
  74  * A directory to be installed/removed.
  75  */
  76 struct dirInfo_s {
  77     const char * dirName;       /*!< Directory path (+ trailing '/'). */
  78     int dirNameLen;             /*!< No. bytes in directory path. */
  79     fileIndexEntry files;       /*!< Array of files in directory. */
  80     int numFiles;               /*!< No. files in directory. */
  81 };
  82
  83 /** \ingroup rpmdep
  84  * Set of available packages, items, and directories.
  85  */
  86 struct rpmal_s {
  87     availablePackage list;      /*!< Set of packages. */
  88     struct availableIndex_s index;      /*!< Set of available items. */
  89     int delta;                  /*!< Delta for pkg list reallocation. */
  90     int size;                   /*!< No. of pkgs in list. */
  91     int alloced;                /*!< No. of pkgs allocated for list. */
  92     uint32_t tscolor;           /*!< Transaction color. */
  93     int numDirs;                /*!< No. of directories. */
  94     dirInfo dirs;               /*!< Set of directories. */
  95 };
  96
  97 /**
  98  * Destroy available item index.
  99  * @param al            available list
 100  */
 101 static void rpmalFreeIndex(rpmal al)
 102 {
 103     availableIndex ai = &al->index;
 104     if (ai->size > 0) {
 105         ai->index = _free(ai->index);
 106         ai->size = 0;
 107     }
 108 }
 109
 110 static inline rpmalNum alKey2Num(const rpmal al,
 111                 rpmalKey pkgKey)
 112 {
 113     return ((rpmalNum)pkgKey);
 114 }
 115
 116 static inline rpmalKey alNum2Key(const rpmal al,
 117                 rpmalNum pkgNum)
 118 {
 119     return ((rpmalKey)pkgNum);
 120 }
 121
 122 rpmal rpmalCreate(int delta)
 123 {
 124     rpmal al = xcalloc(1, sizeof(*al));
 125     availableIndex ai = &al->index;
 126
 127     al->delta = delta;
 128     al->size = 0;
 129     al->list = xcalloc(al->delta, sizeof(*al->list));
 130     al->alloced = al->delta;
 131
 132     ai->index = NULL;
 133     ai->size = 0;
 134
 135     al->numDirs = 0;
 136     al->dirs = NULL;
 137     return al;
 138 }
 139
 140 rpmal rpmalFree(rpmal al)
 141 {
 142     availablePackage alp;
 143     dirInfo die;
 144     int i;
 145
 146     if (al == NULL)
 147         return NULL;
 148
 149     if ((alp = al->list) != NULL)
 150     for (i = 0; i < al->size; i++, alp++) {
 151         alp->provides = rpmdsFree(alp->provides);
 152         alp->fi = rpmfiFree(alp->fi);
 153     }
 154
 155     if ((die = al->dirs) != NULL)
 156     for (i = 0; i < al->numDirs; i++, die++) {
 157         die->dirName = _free(die->dirName);
 158         die->files = _free(die->files);
 159     }
 160     al->dirs = _free(al->dirs);
 161     al->numDirs = 0;
 162
 163     al->list = _free(al->list);
 164     al->alloced = 0;
 165     rpmalFreeIndex(al);
 166     al = _free(al);
 167     return NULL;
 168 }
 169
 170 /**
 171  * Compare two directory info entries by name (qsort/bsearch).
 172  * @param one           1st directory info
 173  * @param two           2nd directory info
 174  * @return              result of comparison
 175  */
 176 static int dieCompare(const void * one, const void * two)
 177 {
 178     const dirInfo a = (const dirInfo) one;
 179     const dirInfo b = (const dirInfo) two;
 180     int lenchk = a->dirNameLen - b->dirNameLen;
 181
 182     if (lenchk || a->dirNameLen == 0)
 183         return lenchk;
 184
 185     if (a->dirName == NULL || b->dirName == NULL)
 186         return lenchk;
 187
 188     /* XXX FIXME: this might do "backward" strcmp for speed */
 189     return strcmp(a->dirName, b->dirName);
 190 }
 191
 192 /**
 193  * Compare two file info entries by name (qsort/bsearch).
 194  * @param one           1st directory info
 195  * @param two           2nd directory info
 196  * @return              result of comparison
 197  */
 198 static int fieCompare(const void * one, const void * two)
 199 {
 200     const fileIndexEntry a = (const fileIndexEntry) one;
 201     const fileIndexEntry b = (const fileIndexEntry) two;
 202     int lenchk = a->baseNameLen - b->baseNameLen;
 203
 204     if (lenchk)
 205         return lenchk;
 206
 207     if (a->baseName == NULL || b->baseName == NULL)
 208         return lenchk;
 209
 210 #ifdef  NOISY
 211 if (_rpmal_debug) {
 212 fprintf(stderr, "\t\tstrcmp(%p:%p, %p:%p)", a, a->baseName, b, b->baseName);
 213 #if 0
 214 fprintf(stderr, " a %s", a->baseName);
 215 #endif
 216 fprintf(stderr, " b %s", a->baseName);
 217 fprintf(stderr, "\n");
 218 }
 219 #endif
 220
 221     return strcmp(a->baseName, b->baseName);
 222 }
 223
 224 void rpmalDel(rpmal al, rpmalKey pkgKey)
 225 {
 226     rpmalNum pkgNum = alKey2Num(al, pkgKey);
 227     availablePackage alp;
 228     rpmfi fi;
 229
 230     if (al == NULL || al->list == NULL)
 231         return;         /* XXX can't happen */
 232
 233     alp = al->list + pkgNum;
 234
 235 if (_rpmal_debug)
 236 fprintf(stderr, "*** del %p[%d]\n", al->list, (int) pkgNum);
 237
 238     /* Delete directory/file info entries from added package list. */
 239     if ((fi = alp->fi) != NULL)
 240     if (rpmfiFC(fi) > 0) {
 241         int origNumDirs = al->numDirs;
 242         int dx;
 243         dirInfo dieNeedle =
 244                 memset(alloca(sizeof(*dieNeedle)), 0, sizeof(*dieNeedle));
 245         dirInfo die;
 246         int last;
 247         int i;
 248
 249         /* XXX FIXME: We ought to relocate the directory list here */
 250
 251         if (al->dirs != NULL)
 252         for (dx = rpmfiDC(fi) - 1; dx >= 0; dx--)
 253         {
 254             fileIndexEntry fie;
 255
 256             (void) rpmfiSetDX(fi, dx);
 257
 258             dieNeedle->dirName = (char *) rpmfiDN(fi);
 259             dieNeedle->dirNameLen = (dieNeedle->dirName != NULL
 260                         ? strlen(dieNeedle->dirName) : 0);
 261             die = bsearch(dieNeedle, al->dirs, al->numDirs,
 262                                sizeof(*dieNeedle), dieCompare);
 263             if (die == NULL)
 264                 continue;
 265
 266 if (_rpmal_debug)
 267 fprintf(stderr, "--- die[%5ld] %p [%3d] %s\n", (die - al->dirs), die, die->dirNameLen, die->dirName);
 268
 269             last = die->numFiles;
 270             fie = die->files + last - 1;
 271             for (i = last - 1; i >= 0; i--, fie--) {
 272                 if (fie->pkgNum != pkgNum)
 273                     continue;
 274                 die->numFiles--;
 275
 276                 if (i < die->numFiles) {
 277 if (_rpmal_debug)
 278 fprintf(stderr, "\t%p[%3d] memmove(%p:%p,%p:%p,0x%lx) %s <- %s\n", die->files, die->numFiles, fie, fie->baseName, fie+1, (fie+1)->baseName, ((die->numFiles - i) * sizeof(*fie)), fie->baseName, (fie+1)->baseName);
 279
 280                     memmove(fie, fie+1, (die->numFiles - i) * sizeof(*fie));
 281                 }
 282 if (_rpmal_debug)
 283 fprintf(stderr, "\t%p[%3d] memset(%p,0,0x%lx) %p [%3d] %s\n", die->files, die->numFiles, die->files + die->numFiles, sizeof(*fie), fie->baseName, fie->baseNameLen, fie->baseName);
 284                 memset(die->files + die->numFiles, 0, sizeof(*fie)); /* overkill */
 285
 286             }
 287             if (die->numFiles > 0) {
 288                 if (last > i)
 289                     die->files = xrealloc(die->files,
 290                                         die->numFiles * sizeof(*die->files));
 291                 continue;
 292             }
 293             die->files = _free(die->files);
 294             die->dirName = _free(die->dirName);
 295             al->numDirs--;
 296             if ((die - al->dirs) < al->numDirs) {
 297 if (_rpmal_debug)
 298 fprintf(stderr, "    die[%5ld] memmove(%p,%p,0x%lx)\n", (die - al->dirs), die, die+1, ((al->numDirs - (die - al->dirs)) * sizeof(*die)));
 299
 300                 memmove(die, die+1, (al->numDirs - (die - al->dirs)) * sizeof(*die));
 301             }
 302
 303 if (_rpmal_debug)
 304 fprintf(stderr, "    die[%5d] memset(%p,0,0x%lx)\n", al->numDirs, al->dirs + al->numDirs, sizeof(*die));
 305             memset(al->dirs + al->numDirs, 0, sizeof(*al->dirs)); /* overkill */
 306         }
 307
 308         if (origNumDirs > al->numDirs) {
 309             if (al->numDirs > 0)
 310                 al->dirs = xrealloc(al->dirs, al->numDirs * sizeof(*al->dirs));
 311             else
 312                 al->dirs = _free(al->dirs);
 313         }
 314     }
 315
 316     alp->provides = rpmdsFree(alp->provides);
 317     alp->fi = rpmfiFree(alp->fi);
 318
 319     memset(alp, 0, sizeof(*alp));       /* XXX trash and burn */
 320     return;
 321 }
 322
 323 rpmalKey rpmalAdd(rpmal * alistp, rpmalKey pkgKey, fnpyKey key,
 324                 rpmds provides, rpmfi fi, uint32_t tscolor)
 325 {
 326     rpmalNum pkgNum;
 327     rpmal al;
 328     availablePackage alp;
 329
 330     /* If list doesn't exist yet, create. */
 331     if (*alistp == NULL)
 332         *alistp = rpmalCreate(5);
 333     al = *alistp;
 334     pkgNum = alKey2Num(al, pkgKey);
 335
 336     if (pkgNum >= 0 && pkgNum < al->size) {
 337         rpmalDel(al, pkgKey);
 338     } else {
 339         if (al->size == al->alloced) {
 340             al->alloced += al->delta;
 341             al->list = xrealloc(al->list, sizeof(*al->list) * al->alloced);
 342         }
 343         pkgNum = al->size++;
 344     }
 345
 346     if (al->list == NULL)
 347         return RPMAL_NOMATCH;           /* XXX can't happen */
 348
 349     alp = al->list + pkgNum;
 350
 351     alp->key = key;
 352     alp->tscolor = tscolor;
 353
 354 if (_rpmal_debug)
 355 fprintf(stderr, "*** add %p[%d] 0x%x\n", al->list, (int) pkgNum, tscolor);
 356
 357     alp->provides = rpmdsLink(provides, "Provides (rpmalAdd)");
 358     alp->fi = rpmfiLink(fi, "Files (rpmalAdd)");
 359
 360     fi = rpmfiLink(alp->fi, "Files index (rpmalAdd)");
 361     fi = rpmfiInit(fi, 0);
 362     if (rpmfiFC(fi) > 0) {
 363         dirInfo dieNeedle =
 364                 memset(alloca(sizeof(*dieNeedle)), 0, sizeof(*dieNeedle));
 365         dirInfo die;
 366         int dc = rpmfiDC(fi);
 367         int dx;
 368         int * dirMapping = alloca(sizeof(*dirMapping) * dc);
 369         int * dirUnique = alloca(sizeof(*dirUnique) * dc);
 370         const char * DN;
 371         int origNumDirs;
 372         int first;
 373         int i = 0;
 374
 375         /* XXX FIXME: We ought to relocate the directory list here */
 376
 377         /* XXX enough space for all directories, late realloc to truncate. */
 378         al->dirs = xrealloc(al->dirs, (al->numDirs + dc) * sizeof(*al->dirs));
 379
 380         /* Only previously allocated dirInfo is sorted and bsearch'able. */
 381         origNumDirs = al->numDirs;
 382
 383         /* Package dirnames are not currently unique. Create unique mapping. */
 384         for (dx = 0; dx < dc; dx++) {
 385             (void) rpmfiSetDX(fi, dx);
 386             DN = rpmfiDN(fi);
 387             if (DN != NULL)
 388             for (i = 0; i < dx; i++) {
 389                 const char * iDN;
 390                 (void) rpmfiSetDX(fi, i);
 391                 iDN = rpmfiDN(fi);
 392                 if (iDN != NULL && !strcmp(DN, iDN))
 393                     break;
 394             }
 395             dirUnique[dx] = i;
 396         }
 397
 398         /* Map package dirs into transaction dirInfo index. */
 399         for (dx = 0; dx < dc; dx++) {
 400
 401             /* Non-unique package dirs use the 1st entry mapping. */
 402             if (dirUnique[dx] < dx) {
 403                 dirMapping[dx] = dirMapping[dirUnique[dx]];
 404                 continue;
 405             }
 406
 407             /* Find global dirInfo mapping for first encounter. */
 408             (void) rpmfiSetDX(fi, dx);
 409
 410             {   DN = rpmfiDN(fi);
 411
 412 #if defined(__ia64__)
 413 /* XXX Make sure that autorelocated file dependencies are satisfied. */
 414 #define DNPREFIX        "/emul/ia32-linux"
 415                 if (!strncmp(DN, DNPREFIX, sizeof(DNPREFIX)-1))
 416                     DN += sizeof(DNPREFIX)-1;
 417 #endif
 418                 dieNeedle->dirName = DN;
 419             }
 420
 421             dieNeedle->dirNameLen = (dieNeedle->dirName != NULL
 422                         ? strlen(dieNeedle->dirName) : 0);
 423             die = bsearch(dieNeedle, al->dirs, origNumDirs,
 424                                sizeof(*dieNeedle), dieCompare);
 425             if (die) {
 426                 dirMapping[dx] = die - al->dirs;
 427             } else {
 428                 dirMapping[dx] = al->numDirs;
 429                 die = al->dirs + al->numDirs;
 430                 if (dieNeedle->dirName != NULL)
 431                     die->dirName = xstrdup(dieNeedle->dirName);
 432                 die->dirNameLen = dieNeedle->dirNameLen;
 433                 die->files = NULL;
 434                 die->numFiles = 0;
 435 if (_rpmal_debug)
 436 fprintf(stderr, "+++ die[%5d] %p [%3d] %s\n", al->numDirs, die, die->dirNameLen, die->dirName);
 437
 438                 al->numDirs++;
 439             }
 440         }
 441
 442         for (first = rpmfiNext(fi); first >= 0;) {
 443             fileIndexEntry fie;
 444             int next;
 445
 446             /* Find the first file of the next directory. */
 447             dx = rpmfiDX(fi);
 448             while ((next = rpmfiNext(fi)) >= 0) {
 449                 if (dx != rpmfiDX(fi))
 450                     break;
 451             }
 452             if (next < 0) next = rpmfiFC(fi);   /* XXX reset end-of-list */
 453
 454             die = al->dirs + dirMapping[dx];
 455             die->files = xrealloc(die->files,
 456                         (die->numFiles + next - first) * sizeof(*die->files));
 457
 458             fie = die->files + die->numFiles;
 459
 460 if (_rpmal_debug)
 461 fprintf(stderr, "    die[%5d] %p->files [%p[%d],%p) -> [%p[%d],%p)\n", dirMapping[dx], die,
 462 die->files, die->numFiles, die->files+die->numFiles,
 463 fie, (next - first), fie + (next - first));
 464
 465             /* Rewind to first file, generate file index entry for each file. */
 466             fi = rpmfiInit(fi, first);
 467             while ((first = rpmfiNext(fi)) >= 0 && first < next) {
 468                 fie->baseName = rpmfiBN(fi);
 469                 fie->baseNameLen = (fie->baseName ? strlen(fie->baseName) : 0);
 470                 fie->pkgNum = pkgNum;
 471                 fie->ficolor = rpmfiFColor(fi);
 472 if (_rpmal_debug)
 473 fprintf(stderr, "\t%p[%3d] %p:%p[%2d] %s\n", die->files, die->numFiles, fie, fie->baseName, fie->baseNameLen, rpmfiFN(fi));
 474
 475                 die->numFiles++;
 476                 fie++;
 477             }
 478             qsort(die->files, die->numFiles, sizeof(*die->files), fieCompare);
 479         }
 480
 481         /* Resize the directory list. If any directories were added, resort. */
 482         al->dirs = xrealloc(al->dirs, al->numDirs * sizeof(*al->dirs));
 483         if (origNumDirs != al->numDirs)
 484             qsort(al->dirs, al->numDirs, sizeof(*al->dirs), dieCompare);
 485     }
 486     fi = rpmfiUnlink(fi, "Files index (rpmalAdd)");
 487
 488     rpmalFreeIndex(al);
 489
 490 assert(((rpmalNum)(alp - al->list)) == pkgNum);
 491     return ((rpmalKey)(alp - al->list));
 492 }
 493
 494 /**
 495  * Compare two available index entries by name (qsort/bsearch).
 496  * @param one           1st available index entry
 497  * @param two           2nd available index entry
 498  * @return              result of comparison
 499  */
 500 static int indexcmp(const void * one, const void * two)
 501 {
 502     const availableIndexEntry a = (const availableIndexEntry) one;
 503     const availableIndexEntry b = (const availableIndexEntry) two;
 504     int lenchk;
 505
 506     lenchk = a->entryLen - b->entryLen;
 507     if (lenchk)
 508         return lenchk;
 509
 510     return strcmp(a->entry, b->entry);
 511 }
 512
 513 void rpmalAddProvides(rpmal al, rpmalKey pkgKey, rpmds provides, uint32_t tscolor)
 514 {
 515     uint32_t dscolor;
 516     const char * Name;
 517     rpmalNum pkgNum = alKey2Num(al, pkgKey);
 518     availableIndex ai = &al->index;
 519     availableIndexEntry aie;
 520     int ix;
 521
 522     if (provides == NULL || pkgNum < 0 || pkgNum >= al->size)
 523         return;
 524     if (ai->index == NULL || ai->k < 0 || ai->k >= ai->size)
 525         return;
 526
 527     if (rpmdsInit(provides) != NULL)
 528     while (rpmdsNext(provides) >= 0) {
 529
 530         if ((Name = rpmdsN(provides)) == NULL)
 531             continue;   /* XXX can't happen */
 532
 533         /* Ignore colored provides not in our rainbow. */
 534         dscolor = rpmdsColor(provides);
 535         if (tscolor && dscolor && !(tscolor & dscolor))
 536             continue;
 537
 538         aie = ai->index + ai->k;
 539         ai->k++;
 540
 541         aie->pkgKey = pkgKey;
 542         aie->entry = Name;
 543         aie->entryLen = strlen(Name);
 544         ix = rpmdsIx(provides);
 545
 546 /* XXX make sure that element index fits in unsigned short */
 547 assert(ix < 0x10000);
 548
 549         aie->entryIx = ix;
 550         aie->type = IET_PROVIDES;
 551     }
 552 }
 553
 554 void rpmalMakeIndex(rpmal al)
 555 {
 556     availableIndex ai;
 557     availablePackage alp;
 558     intptr_t i;
 559
 560     if (al == NULL || al->list == NULL) return;
 561     ai = &al->index;
 562
 563     ai->size = 0;
 564     for (i = 0; i < al->size; i++) {
 565         alp = al->list + i;
 566         if (alp->provides != NULL)
 567             ai->size += rpmdsCount(alp->provides);
 568     }
 569     if (ai->size == 0) return;
 570
 571     ai->index = xrealloc(ai->index, ai->size * sizeof(*ai->index));
 572     ai->k = 0;
 573     for (i = 0; i < al->size; i++) {
 574         alp = al->list + i;
 575         rpmalAddProvides(al, (rpmalKey)i, alp->provides, alp->tscolor);
 576     }
 577
 578     /* Reset size to the no. of provides added. */
 579     ai->size = ai->k;
 580     qsort(ai->index, ai->size, sizeof(*ai->index), indexcmp);
 581 }
 582
 583 fnpyKey *
 584 rpmalAllFileSatisfiesDepend(const rpmal al, const rpmds ds, rpmalKey * keyp)
 585 {
 586     uint32_t tscolor;
 587     uint32_t ficolor;
 588     int found = 0;
 589     const char * dirName;
 590     const char * baseName;
 591     dirInfo dieNeedle =
 592                 memset(alloca(sizeof(*dieNeedle)), 0, sizeof(*dieNeedle));
 593     dirInfo die;
 594     fileIndexEntry fieNeedle =
 595                 memset(alloca(sizeof(*fieNeedle)), 0, sizeof(*fieNeedle));
 596     fileIndexEntry fie;
 597     availablePackage alp;
 598     fnpyKey * ret = NULL;
 599     const char * fileName;
 600
 601     if (keyp) *keyp = RPMAL_NOMATCH;
 602
 603     if (al == NULL || (fileName = rpmdsN(ds)) == NULL || *fileName != '/')
 604         return NULL;
 605
 606     /* Solaris 2.6 bsearch sucks down on this. */
 607     if (al->numDirs == 0 || al->dirs == NULL || al->list == NULL)
 608         return NULL;
 609
 610     {   char * t;
 611         dirName = t = xstrdup(fileName);
 612         if ((t = strrchr(t, '/')) != NULL) {
 613             t++;                /* leave the trailing '/' */
 614             *t = '\0';
 615         }
 616     }
 617
 618     dieNeedle->dirName = (char *) dirName;
 619     dieNeedle->dirNameLen = strlen(dirName);
 620     die = bsearch(dieNeedle, al->dirs, al->numDirs,
 621                        sizeof(*dieNeedle), dieCompare);
 622     if (die == NULL)
 623         goto exit;
 624
 625     /* rewind to the first match */
 626     while (die > al->dirs && dieCompare(die-1, dieNeedle) == 0)
 627         die--;
 628
 629     if ((baseName = strrchr(fileName, '/')) == NULL)
 630         goto exit;
 631     baseName++;
 632
 633     /* FIX: ret is a problem */
 634     for (found = 0, ret = NULL;
 635          die < al->dirs + al->numDirs && dieCompare(die, dieNeedle) == 0;
 636          die++)
 637     {
 638
 639 if (_rpmal_debug)
 640 fprintf(stderr, "==> die %p %s\n", die, (die->dirName ? die->dirName : "(nil)"));
 641
 642         fieNeedle->baseName = baseName;
 643         fieNeedle->baseNameLen = strlen(fieNeedle->baseName);
 644         fie = bsearch(fieNeedle, die->files, die->numFiles,
 645                        sizeof(*fieNeedle), fieCompare);
 646         if (fie == NULL)
 647             continue;   /* XXX shouldn't happen */
 648
 649 if (_rpmal_debug)
 650 fprintf(stderr, "==> fie %p %s\n", fie, (fie->baseName ? fie->baseName : "(nil)"));
 651
 652         alp = al->list + fie->pkgNum;
 653
 654         /* Ignore colored files not in our rainbow. */
 655         tscolor = alp->tscolor;
 656         ficolor = fie->ficolor;
 657         if (tscolor && ficolor && !(tscolor & ficolor))
 658             continue;
 659
 660         rpmdsNotify(ds, _("(added files)"), 0);
 661
 662         ret = xrealloc(ret, (found+2) * sizeof(*ret));
 663         if (ret)        /* can't happen */
 664             ret[found] = alp->key;
 665         if (keyp)
 666             *keyp = alNum2Key(al, fie->pkgNum);
 667         found++;
 668     }
 669
 670 exit:
 671     dirName = _free(dirName);
 672     if (ret)
 673         ret[found] = NULL;
 674     return ret;
 675 }
 676
 677 fnpyKey *
 678 rpmalAllSatisfiesDepend(const rpmal al, const rpmds ds, rpmalKey * keyp)
 679 {
 680     availableIndex ai;
 681     availableIndexEntry needle;
 682     availableIndexEntry match;
 683     fnpyKey * ret = NULL;
 684     int found = 0;
 685     const char * KName;
 686     availablePackage alp;
 687     int rc;
 688
 689     if (keyp) *keyp = RPMAL_NOMATCH;
 690
 691     if (al == NULL || ds == NULL || (KName = rpmdsN(ds)) == NULL)
 692         return ret;
 693
 694     if (*KName == '/') {
 695         /* First, look for files "contained" in package ... */
 696         ret = rpmalAllFileSatisfiesDepend(al, ds, keyp);
 697         if (ret != NULL && *ret != NULL)
 698             return ret;
 699         /* ... then, look for files "provided" by package. */
 700         ret = _free(ret);
 701     }
 702
 703     ai = &al->index;
 704     if (ai->index == NULL || ai->size <= 0)
 705         return NULL;
 706
 707     needle = memset(alloca(sizeof(*needle)), 0, sizeof(*needle));
 708     needle->entry = KName;
 709     needle->entryLen = strlen(needle->entry);
 710
 711     match = bsearch(needle, ai->index, ai->size, sizeof(*ai->index), indexcmp);
 712     if (match == NULL)
 713         return NULL;
 714
 715     /* rewind to the first match */
 716     while (match > ai->index && indexcmp(match-1, needle) == 0)
 717         match--;
 718
 719     if (al->list != NULL)       /* XXX always true */
 720     for (ret = NULL, found = 0;
 721          match < ai->index + ai->size && indexcmp(match, needle) == 0;
 722          match++)
 723     {
 724         alp = al->list + alKey2Num(al, match->pkgKey);
 725
 726         rc = 0;
 727         if (alp->provides != NULL)      /* XXX can't happen */
 728         switch (match->type) {
 729         case IET_PROVIDES:
 730             /* XXX single step on rpmdsNext to regenerate DNEVR string */
 731             (void) rpmdsSetIx(alp->provides, match->entryIx - 1);
 732             if (rpmdsNext(alp->provides) >= 0)
 733                 rc = rpmdsCompare(alp->provides, ds);
 734
 735             if (rc)
 736                 rpmdsNotify(ds, _("(added provide)"), 0);
 737
 738             break;
 739         }
 740
 741         if (rc) {
 742             ret = xrealloc(ret, (found + 2) * sizeof(*ret));
 743             if (ret)    /* can't happen */
 744                 ret[found] = alp->key;
 745             if (keyp)
 746                 *keyp = match->pkgKey;
 747             found++;
 748         }
 749     }
 750
 751     if (ret)
 752         ret[found] = NULL;
 753
 754 /* FIX: *keyp may be NULL */
 755     return ret;
 756 }
 757
 758 fnpyKey
 759 rpmalSatisfiesDepend(const rpmal al, const rpmds ds, rpmalKey * keyp)
 760 {
 761     fnpyKey * tmp = rpmalAllSatisfiesDepend(al, ds, keyp);
 762
 763     if (tmp) {
 764         fnpyKey ret = tmp[0];
 765         free(tmp);
 766         return ret;
 767     }
 768     return NULL;
 769 }