lib/rpmal.c

   1 /** \ingroup rpmdep
   2  * \file lib/rpmal.c
   3  */
   4
   5 #include "system.h"
   6
   7
   8 #include <rpm/rpmds.h>
   9 #include <rpm/rpmte.h>
  10 #include <rpm/rpmfi.h>
  11
  12 #include "lib/rpmal.h"
  13 #include "lib/misc.h"
  14
  15 #include "debug.h"
  16
  17 typedef struct availablePackage_s * availablePackage;
  18 typedef int rpmalNum;
  19
  20 /** \ingroup rpmdep
  21  * Info about a single package to be installed.
  22  */
  23 struct availablePackage_s {
  24     rpmte p;                    /*!< transaction member */
  25     rpmds provides;             /*!< Provides: dependencies. */
  26     rpmfi fi;                   /*!< File info set. */
  27 };
  28
  29 typedef struct availableIndexEntry_s *  availableIndexEntry;
  30
  31 /** \ingroup rpmdep
  32  * A single available item (e.g. a Provides: dependency).
  33  */
  34 struct availableIndexEntry_s {
  35     rpmalNum pkgNum;            /*!< Containing package index. */
  36     unsigned int entryIx;       /*!< Dependency index. */
  37 };
  38
  39 struct fileNameEntry_s {
  40     const char * dirName;
  41     const char * baseName;
  42 };
  43
  44
  45 /** \ingroup rpmdep
  46  * A file to be installed/removed.
  47  */
  48 typedef struct fileIndexEntry_s * fileIndex;
  49
  50 struct fileIndexEntry_s {
  51     rpmalNum pkgNum;            /*!< Containing package index. */
  52     unsigned int entryIx;
  53 };
  54
  55 #undef HASHTYPE
  56 #undef HTKEYTYPE
  57 #undef HTDATATYPE
  58 #define HASHTYPE rpmalProvidesHash
  59 #define HTKEYTYPE const char *
  60 #define HTDATATYPE struct availableIndexEntry_s
  61 #include "lib/rpmhash.H"
  62 #include "lib/rpmhash.C"
  63
  64 #undef HASHTYPE
  65 #undef HTKEYTYPE
  66 #undef HTDATATYPE
  67 #define HASHTYPE rpmalFileHash
  68 #define HTKEYTYPE struct fileNameEntry_s
  69 #define HTDATATYPE struct fileIndexEntry_s
  70 #include "lib/rpmhash.H"
  71 #include "lib/rpmhash.C"
  72
  73
  74
  75 /** \ingroup rpmdep
  76  * Set of available packages, items, and directories.
  77  */
  78 struct rpmal_s {
  79     availablePackage list;      /*!< Set of packages. */
  80     rpmalProvidesHash providesHash;
  81     rpmalFileHash fileHash;
  82     int delta;                  /*!< Delta for pkg list reallocation. */
  83     int size;                   /*!< No. of pkgs in list. */
  84     int alloced;                /*!< No. of pkgs allocated for list. */
  85     rpm_color_t tscolor;        /*!< Transaction color. */
  86     rpm_color_t prefcolor;      /*!< Transaction preferred color. */
  87 };
  88
  89 /**
  90  * Destroy available item index.
  91  * @param al            available list
  92  */
  93 static void rpmalFreeIndex(rpmal al)
  94 {
  95     al->providesHash = rpmalProvidesHashFree(al->providesHash);
  96     al->fileHash = rpmalFileHashFree(al->fileHash);
  97 }
  98
  99 rpmal rpmalCreate(int delta, rpm_color_t tscolor, rpm_color_t prefcolor)
 100 {
 101     rpmal al = xcalloc(1, sizeof(*al));
 102
 103     al->delta = delta;
 104     al->size = 0;
 105     al->alloced = al->delta;
 106     al->list = xmalloc(sizeof(*al->list) * al->alloced);;
 107
 108     al->providesHash = NULL;
 109     al->fileHash = NULL;
 110     al->tscolor = tscolor;
 111     al->prefcolor = prefcolor;
 112
 113     return al;
 114 }
 115
 116 rpmal rpmalFree(rpmal al)
 117 {
 118     availablePackage alp;
 119     int i;
 120
 121     if (al == NULL)
 122         return NULL;
 123
 124     if ((alp = al->list) != NULL)
 125     for (i = 0; i < al->size; i++, alp++) {
 126         alp->provides = rpmdsFree(alp->provides);
 127         alp->fi = rpmfiFree(alp->fi);
 128     }
 129     al->list = _free(al->list);
 130     al->alloced = 0;
 131
 132     rpmalFreeIndex(al);
 133     al = _free(al);
 134     return NULL;
 135 }
 136
 137 static unsigned int fileHash(struct fileNameEntry_s file){
 138     return hashFunctionString(file.dirName) ^ hashFunctionString(file.baseName);
 139 }
 140
 141 static int fileCompare(struct fileNameEntry_s one, struct fileNameEntry_s two) {
 142     int rc = 0;
 143     rc = strcmp(one.dirName, two.dirName);
 144     if (!rc)
 145         rc = strcmp(one.baseName, two.baseName);
 146     return rc;
 147 }
 148
 149 void rpmalDel(rpmal al, rpmte p)
 150 {
 151     availablePackage alp;
 152     rpmalNum pkgNum;
 153
 154     if (al == NULL || al->list == NULL)
 155         return;         /* XXX can't happen */
 156
 157     // XXX use a search for self provide
 158     for (pkgNum=0; pkgNum<al->size; pkgNum++) {
 159         if (al->list[pkgNum].p == p) {
 160             break;
 161         }
 162     }
 163     if (pkgNum == al->size ) return; // Not found!
 164
 165     alp = al->list + pkgNum;
 166     // do not actually delete, just set p to NULL
 167     // and later filter that out of the results
 168     alp->p = NULL;
 169 }
 170
 171 static void rpmalAddFiles(rpmal al, rpmalNum pkgNum, rpmfi fi){
 172     struct fileNameEntry_s fileName;
 173     struct fileIndexEntry_s fileEntry;
 174     int i;
 175     rpm_color_t ficolor;
 176
 177     fileEntry.pkgNum = pkgNum;
 178
 179     fi = rpmfiInit(fi, 0);
 180     while ((i = rpmfiNext(fi)) >= 0) {
 181         /* Ignore colored provides not in our rainbow. */
 182         ficolor = rpmfiFColor(fi);
 183         if (al->tscolor && ficolor && !(al->tscolor & ficolor))
 184             continue;
 185
 186         fileName.dirName = rpmfiDN(fi);
 187         fileName.baseName = rpmfiBN(fi);
 188
 189         fileEntry.entryIx = i;
 190
 191         rpmalFileHashAddEntry(al->fileHash, fileName, fileEntry);
 192     }
 193 }
 194
 195 static void rpmalAddProvides(rpmal al, rpmalNum pkgNum, rpmds provides){
 196     struct availableIndexEntry_s indexEntry;
 197     rpm_color_t dscolor;
 198
 199     indexEntry.pkgNum = pkgNum;
 200
 201     if (rpmdsInit(provides) != NULL)
 202     while (rpmdsNext(provides) >= 0) {
 203         /* Ignore colored provides not in our rainbow. */
 204         dscolor = rpmdsColor(provides);
 205         if (al->tscolor && dscolor && !(al->tscolor & dscolor))
 206             continue;
 207
 208         indexEntry.entryIx = rpmdsIx(provides);
 209         rpmalProvidesHashAddEntry(al->providesHash, rpmdsN(provides), indexEntry);
 210     }
 211 }
 212
 213 void rpmalAdd(rpmal al, rpmte p)
 214 {
 215     rpmalNum pkgNum;
 216     availablePackage alp;
 217
 218     if (al->size == al->alloced) {
 219         al->alloced += al->delta;
 220         al->list = xrealloc(al->list, sizeof(*al->list) * al->alloced);
 221     }
 222     pkgNum = al->size++;
 223
 224     alp = al->list + pkgNum;
 225
 226     alp->p = p;
 227
 228     alp->provides = rpmdsLink(rpmteDS(p, RPMTAG_PROVIDENAME));
 229     alp->fi = rpmfiLink(rpmteFI(p));
 230
 231     if (al->providesHash != NULL) { // index is already created
 232         rpmalAddProvides(al, pkgNum, alp->provides);
 233         rpmalAddFiles(al, pkgNum, alp->fi);
 234     }
 235
 236     assert(((rpmalNum)(alp - al->list)) == pkgNum);
 237 }
 238
 239 static void rpmalMakeIndex(rpmal al)
 240 {
 241     availablePackage alp;
 242     int i;
 243     int providesCnt = 0;
 244     int fileCnt = 0;
 245
 246     if (al == NULL || al->list == NULL) return;
 247     if (al->providesHash != NULL || al->fileHash != NULL)
 248         return;
 249     for (i = 0; i < al->size; i++) {
 250         alp = al->list + i;
 251         if (alp->provides != NULL)
 252             providesCnt += rpmdsCount(alp->provides);
 253         if (alp->fi != NULL)
 254             fileCnt += rpmfiFC(alp->fi);
 255     }
 256
 257     al->providesHash = rpmalProvidesHashCreate(providesCnt/4+128, hashFunctionString,
 258                                                strcmp, NULL, NULL);
 259     al->fileHash = rpmalFileHashCreate(fileCnt/4+128, fileHash, fileCompare,
 260                                        NULL, NULL);
 261
 262     for (i = 0; i < al->size; i++) {
 263         alp = al->list + i;
 264         rpmalAddProvides(al, i, alp->provides);
 265         rpmalAddFiles(al, i, alp->fi);
 266     }
 267 }
 268
 269 static rpmte * rpmalAllFileSatisfiesDepend(const rpmal al, const rpmds ds)
 270 {
 271     const char *fileName = rpmdsN(ds);
 272     const char *slash;
 273     rpmte * ret = NULL;
 274
 275     if (al == NULL || fileName == NULL || *fileName != '/')
 276         return NULL;
 277
 278     /* Split path into dirname and basename components for lookup */
 279     if ((slash = strrchr(fileName, '/')) != NULL) {
 280         fileIndex result;
 281         int resultCnt = 0;
 282         size_t bnStart = (slash - fileName) + 1;
 283         char dirName[bnStart + 1];
 284         struct fileNameEntry_s fne = {
 285             .baseName = fileName + bnStart,
 286             .dirName = dirName,
 287         };
 288         strncpy(dirName, fileName, bnStart);
 289         dirName[bnStart] = '\0';
 290
 291         rpmalFileHashGetEntry(al->fileHash, fne, &result, &resultCnt, NULL);
 292
 293         if (resultCnt > 0) {
 294             int i, found;
 295             ret = xmalloc((resultCnt+1) * sizeof(*ret));
 296
 297             for (found = i = 0; i < resultCnt; i++) {
 298                 availablePackage alp = al->list + result[i].pkgNum;
 299                 if (alp->p == NULL) // deleted
 300                     continue;
 301
 302                 rpmdsNotify(ds, "(added files)", 0);
 303
 304                 ret[found] = alp->p;
 305                 found++;
 306             }
 307             ret[found] = NULL;
 308         }
 309     }
 310
 311     return ret;
 312 }
 313
 314 static rpmte * rpmalAllSatisfiesDepend(const rpmal al, const rpmds ds)
 315 {
 316     rpmte * ret = NULL;
 317     int i, found;
 318     const char * name;
 319     availableIndexEntry result;
 320     int resultCnt;
 321
 322     availablePackage alp;
 323     int rc;
 324
 325     if (al == NULL || ds == NULL || (name = rpmdsN(ds)) == NULL)
 326         return ret;
 327
 328     if (al->providesHash == NULL && al->fileHash == NULL)
 329         rpmalMakeIndex(al);
 330
 331     if (*name == '/') {
 332         /* First, look for files "contained" in package ... */
 333         ret = rpmalAllFileSatisfiesDepend(al, ds);
 334         if (ret != NULL && *ret != NULL)
 335             return ret;
 336         /* ... then, look for files "provided" by package. */
 337         ret = _free(ret);
 338     }
 339
 340     rpmalProvidesHashGetEntry(al->providesHash, name, &result,
 341                               &resultCnt, NULL);
 342
 343     if (resultCnt==0) return NULL;
 344
 345     ret = xmalloc((resultCnt+1) * sizeof(*ret));
 346
 347     for (found=i=0; i<resultCnt; i++) {
 348         alp = al->list + result[i].pkgNum;
 349         if (alp->p == NULL) // deleted
 350             continue;
 351         (void) rpmdsSetIx(alp->provides, result[i].entryIx);
 352         rc = 0;
 353         if (rpmdsIx(alp->provides) >= 0)
 354             rc = rpmdsCompare(alp->provides, ds);
 355
 356         if (rc) {
 357             rpmdsNotify(ds, "(added provide)", 0);
 358             ret[found] = alp->p;
 359             found++;
 360         }
 361     }
 362     ret[found] = NULL;
 363
 364     return ret;
 365 }
 366
 367 rpmte
 368 rpmalSatisfiesDepend(const rpmal al, const rpmds ds)
 369 {
 370     rpmte *providers = rpmalAllSatisfiesDepend(al, ds);
 371     rpmte best = NULL;
 372
 373     if (providers) {
 374         if (al->tscolor) {
 375             /*
 376              * For colored dependencies, try to find a matching provider.
 377              * Otherwise prefer provider of ts preferred color.
 378              */
 379             rpm_color_t dscolor = rpmdsColor(ds);
 380             for (rpmte *p = providers; *p; p++) {
 381                 rpm_color_t tecolor = rpmteColor(*p);
 382                 if (dscolor) {
 383                     if (dscolor == tecolor) best = *p;
 384                 } else if (al->prefcolor) {
 385                     if (al->prefcolor == tecolor) best = *p;
 386                 }
 387                 if (best) break;
 388             }
 389         }
 390         /* if not decided by now, just pick first match */
 391         if (!best) best = providers[0];
 392         free(providers);
 393     }
 394     return best;
 395 }