ext/pool_fileconflicts.c

   1 /*
   2  * Copyright (c) 2009-2013, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 #include <stdio.h>
   9 #include <sys/stat.h>
  10 #include <unistd.h>
  11
  12 #include "pool.h"
  13 #include "repo.h"
  14 #include "hash.h"
  15 #include "repo_rpmdb.h"
  16 #include "pool_fileconflicts.h"
  17
  18 struct cbdata {
  19   Pool *pool;
  20   int create;
  21   int aliases;
  22
  23   Queue lookat;         /* conflict candidates */
  24   Queue lookat_dir;     /* not yet conflicting directories */
  25
  26   Hashtable cflmap;
  27   Hashval cflmapn;
  28   unsigned int cflmapused;
  29
  30   Hashtable dirmap;
  31   Hashval dirmapn;
  32   unsigned int dirmapused;
  33   int dirconflicts;
  34
  35   Map idxmap;
  36
  37   unsigned int lastdiridx;      /* last diridx we have seen */
  38   unsigned int lastdirhash;     /* strhash of last dir we have seen */
  39   int lastdiridxbad;
  40
  41   Id idx;       /* index of package we're looking at */
  42
  43   unsigned char *filesspace;
  44   unsigned int filesspacen;
  45
  46   Hashtable normap;
  47   Hashval normapn;
  48   unsigned int normapused;
  49   Queue norq;
  50
  51   Hashtable statmap;
  52   Hashval statmapn;
  53   unsigned int statmapused;
  54
  55   int usestat;
  56   int statsmade;
  57
  58   const char *rootdir;
  59   int rootdirl;
  60
  61   char *canonspace;
  62   int canonspacen;
  63
  64   Hashtable fetchmap;
  65   Hashval fetchmapn;
  66   Map fetchdirmap;
  67   int fetchdirmapn;
  68   Queue newlookat;
  69 };
  70
  71 #define FILESSPACE_BLOCK 255
  72
  73 static Hashtable
  74 growhash(Hashtable map, Hashval *mapnp)
  75 {
  76   Hashval mapn = *mapnp;
  77   Hashval newn = (mapn + 1) * 2 - 1;
  78   Hashval i, h, hh;
  79   Hashtable m;
  80   Id hx, qx;
  81
  82   m = solv_calloc(newn + 1, 2 * sizeof(Id));
  83   for (i = 0; i <= mapn; i++)
  84     {
  85       hx = map[2 * i];
  86       if (!hx)
  87         continue;
  88       h = hx & newn;
  89       hh = HASHCHAIN_START;
  90       for (;;)
  91         {
  92           qx = m[2 * h];
  93           if (!qx)
  94             break;
  95           h = HASHCHAIN_NEXT(h, hh, newn);
  96         }
  97       m[2 * h] = hx;
  98       m[2 * h + 1] = map[2 * i + 1];
  99     }
 100   solv_free(map);
 101   *mapnp = newn;
 102   return m;
 103 }
 104
 105 /* first pass for non-alias mode:
 106  * create hash (dhx, idx) of directories that may have conflicts.
 107  * also create map "ixdmap" of packages involved
 108  */
 109 static void
 110 finddirs_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 111 {
 112   struct cbdata *cbdata = cbdatav;
 113   Hashval h, hh;
 114   Id dhx, qx;
 115   Id oidx, idx = cbdata->idx;
 116
 117   dhx = strhash(fn);
 118   if (!dhx)
 119     dhx = strlen(fn) + 1;       /* make sure dhx is not zero */
 120   h = dhx & cbdata->dirmapn;
 121   hh = HASHCHAIN_START;
 122   for (;;)
 123     {
 124       qx = cbdata->dirmap[2 * h];
 125       if (!qx)
 126         break;
 127       if (qx == dhx)
 128         break;
 129       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
 130     }
 131   if (!qx)
 132     {
 133       /* a miss */
 134       if (!cbdata->create)
 135         return;
 136       cbdata->dirmap[2 * h] = dhx;
 137       cbdata->dirmap[2 * h + 1] = idx;
 138       if (++cbdata->dirmapused * 2 > cbdata->dirmapn)
 139         cbdata->dirmap = growhash(cbdata->dirmap, &cbdata->dirmapn);
 140       return;
 141     }
 142   /* we saw this dir before */
 143   oidx = cbdata->dirmap[2 * h + 1];
 144   if (oidx == idx)
 145     return;
 146   /* found a conflict, this dir may be used in multiple packages */
 147   if (oidx != -1)
 148     {
 149       MAPSET(&cbdata->idxmap, oidx);
 150       cbdata->dirmap[2 * h + 1] = -1;   /* mark as "multiple packages" */
 151       cbdata->dirconflicts++;
 152     }
 153   MAPSET(&cbdata->idxmap, idx);
 154 }
 155
 156 /* check if a dhx value is marked as "multiple" in the dirmap created by finddirs_cb */
 157 static inline int
 158 isindirmap(struct cbdata *cbdata, Id dhx)
 159 {
 160   Hashval h, hh;
 161   Id qx;
 162
 163   h = dhx & cbdata->dirmapn;
 164   hh = HASHCHAIN_START;
 165   for (;;)
 166     {
 167       qx = cbdata->dirmap[2 * h];
 168       if (!qx)
 169         return 0;
 170       if (qx == dhx)
 171         return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
 172       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
 173     }
 174 }
 175
 176 /* collect all possible file conflicts candidates in cbdata->lookat */
 177 /* algorithm: hash file name into hx. Use cflmap the check if we have seen
 178  * this value before. If yes, we have a file conflict candidate. */
 179 /* we also do extra work to ignore all-directory conflicts */
 180 static void
 181 findfileconflicts_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 182 {
 183   struct cbdata *cbdata = cbdatav;
 184   int isdir = S_ISDIR(info->mode);
 185   const char *dp;
 186   Id idx, oidx;
 187   Id hx, qx;
 188   Hashval h, hh, dhx;
 189
 190   idx = cbdata->idx;
 191
 192   if (!info->dirlen)
 193     return;
 194   dp = fn + info->dirlen;
 195   if (info->diridx != cbdata->lastdiridx)
 196     {
 197       cbdata->lastdiridx = info->diridx;
 198       cbdata->lastdirhash = strnhash(fn, dp - fn);
 199     }
 200   dhx = cbdata->lastdirhash;
 201
 202   /* check if the directory is marked as "multiple" in the dirmap */
 203   /* this mirrors the "if (!dhx) dhx = strlen(fn) + 1" used in  finddirs_cb */
 204   if (!isindirmap(cbdata, dhx ? dhx : dp - fn + 1))
 205     return;
 206
 207   hx = strhash_cont(dp, dhx);   /* extend hash to complete file name */
 208   if (!hx)
 209     hx = strlen(fn) + 1;        /* make sure hx is not zero */
 210
 211   h = hx & cbdata->cflmapn;
 212   hh = HASHCHAIN_START;
 213   for (;;)
 214     {
 215       qx = cbdata->cflmap[2 * h];
 216       if (!qx)
 217         break;
 218       if (qx == hx)
 219         break;
 220       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 221     }
 222   if (!qx)
 223     {
 224       /* a miss */
 225       if (!cbdata->create)
 226         return;
 227       cbdata->cflmap[2 * h] = hx;
 228       cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
 229       if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
 230         cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
 231       return;
 232     }
 233   /* we have seen this hx before */
 234   oidx = cbdata->cflmap[2 * h + 1];
 235   if (oidx < 0)
 236     {
 237       int i;
 238       if (isdir)
 239         {
 240           /* both are directories. delay the conflict, keep oidx in slot */
 241           queue_push2(&cbdata->lookat_dir, hx, idx);
 242           return;
 243         }
 244       oidx = ~oidx;
 245       /* now have file, had directories before. */
 246       cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
 247       /* dump all delayed directory hits for hx */
 248       for (i = 0; i < cbdata->lookat_dir.count; i += 2)
 249         if (cbdata->lookat_dir.elements[i] == hx)
 250           {
 251             queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
 252             queue_push2(&cbdata->lookat, 0, 0);
 253           }
 254     }
 255   else if (oidx == idx)
 256     return;     /* no conflicts with ourself, please */
 257   queue_push2(&cbdata->lookat, hx, oidx);
 258   queue_push2(&cbdata->lookat, 0, 0);
 259   queue_push2(&cbdata->lookat, hx, idx);
 260   queue_push2(&cbdata->lookat, 0, 0);
 261 }
 262
 263 /* same as findfileconflicts_cb, but
 264  * - hashes with just the basename
 265  * - sets idx in a map instead of pushing to lookat
 266  * - sets the hash element to -1 ("multiple") if there may be a conflict
 267  * we then use findfileconflicts_alias_cb as second step to generate the candidates.
 268  * we do it this way because normailzing file names is expensive and thus we
 269  * only want to do it for entries marked as "multiple"
 270  */
 271 static void
 272 findfileconflicts_basename_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 273 {
 274   struct cbdata *cbdata = cbdatav;
 275   int isdir = S_ISDIR(info->mode);
 276   const char *dp;
 277   Id idx, oidx;
 278   Id hx, qx;
 279   Hashval h, hh;
 280
 281   idx = cbdata->idx;
 282
 283   if (!info->dirlen)
 284     return;
 285   dp = fn + info->dirlen;
 286   hx = strhash(dp);
 287   if (!hx)
 288     hx = strlen(fn) + 1;
 289
 290   h = hx & cbdata->cflmapn;
 291   hh = HASHCHAIN_START;
 292   for (;;)
 293     {
 294       qx = cbdata->cflmap[2 * h];
 295       if (!qx)
 296         break;
 297       if (qx == hx)
 298         break;
 299       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 300     }
 301   if (!qx)
 302     {
 303       /* a miss */
 304       if (!cbdata->create)
 305         return;
 306       cbdata->cflmap[2 * h] = hx;
 307       cbdata->cflmap[2 * h + 1] = (isdir ? -idx - 2 : idx);
 308       if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
 309         cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
 310       return;
 311     }
 312   oidx = cbdata->cflmap[2 * h + 1];
 313   if (oidx < -1)
 314     {
 315       int i;
 316       if (isdir)
 317         {
 318           /* both are directories. delay the conflict, keep oidx in slot */
 319           queue_push2(&cbdata->lookat_dir, hx, idx);
 320           return;
 321         }
 322       oidx = -idx - 2;
 323       /* now have file, had directories before. */
 324       cbdata->cflmap[2 * h + 1] = oidx; /* make it a file */
 325       /* dump all delayed directory hits for hx */
 326       for (i = 0; i < cbdata->lookat_dir.count; i += 2)
 327         if (cbdata->lookat_dir.elements[i] == hx)
 328           MAPSET(&cbdata->idxmap, cbdata->lookat_dir.elements[i + 1]);
 329     }
 330   else if (oidx == idx)
 331     return;     /* no conflicts with ourself, please */
 332   if (oidx >= 0)
 333     MAPSET(&cbdata->idxmap, oidx);
 334   MAPSET(&cbdata->idxmap, idx);
 335   if (oidx != -1)
 336     cbdata->cflmap[2 * h + 1] = -1;
 337 }
 338
 339 static inline Id
 340 addfilesspace(struct cbdata *cbdata, int len)
 341 {
 342   unsigned int off = cbdata->filesspacen;
 343   cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
 344   cbdata->filesspacen += len;
 345   return off;
 346 }
 347
 348 static Id
 349 unifywithstat(struct cbdata *cbdata, Id diroff, int dirl)
 350 {
 351   struct stat stb;
 352   int i;
 353   Hashval h, hh;
 354   Id hx, qx;
 355   Id nspaceoff;
 356   unsigned char statdata[16 + sizeof(stb.st_dev) + sizeof(stb.st_ino)];
 357
 358   if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == '/')
 359     cbdata->filesspace[diroff + dirl - 1] = 0;
 360   cbdata->statsmade++;
 361   i = stat((char *)cbdata->filesspace + diroff, &stb);
 362   if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == 0)
 363     cbdata->filesspace[diroff + dirl - 1] = '/';
 364   if (i)
 365     return diroff;
 366   memset(statdata, 0, 16);
 367   memcpy(statdata + 8, &stb.st_dev, sizeof(stb.st_dev));
 368   memcpy(statdata, &stb.st_ino, sizeof(stb.st_ino));
 369   hx = 0;
 370   for (i = 15; i >= 0; i--)
 371     hx = (unsigned int)hx * 13 + statdata[i];
 372   h = hx & cbdata->statmapn;
 373   hh = HASHCHAIN_START;
 374   for (;;)
 375     {
 376       qx = cbdata->statmap[2 * h];
 377       if (!qx)
 378         break;
 379       if (qx == hx)
 380         {
 381           Id off = cbdata->statmap[2 * h + 1];
 382           char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
 383           if (!memcmp(dp, statdata, 16))
 384             return cbdata->norq.elements[off + 1];
 385         }
 386       h = HASHCHAIN_NEXT(h, hh, cbdata->statmapn);
 387     }
 388   /* new stat result. work. */
 389   nspaceoff = addfilesspace(cbdata, 16);
 390   memcpy(cbdata->filesspace + nspaceoff, statdata, 16);
 391   queue_push2(&cbdata->norq, nspaceoff, nspaceoff);
 392   cbdata->statmap[2 * h] = hx;
 393   cbdata->statmap[2 * h + 1] = cbdata->norq.count - 2;
 394   if (++cbdata->statmapused * 2 > cbdata->statmapn)
 395     cbdata->statmap = growhash(cbdata->statmap, &cbdata->statmapn);
 396   return nspaceoff;
 397 }
 398
 399 /* forward declaration */
 400 static Id normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create);
 401
 402 static Id
 403 unifywithcanon(struct cbdata *cbdata, Id diroff, int dirl)
 404 {
 405   Id dirnameid;
 406   int i, l, ll, lo;
 407   struct stat stb;
 408
 409 #if 0
 410   printf("UNIFY %.*s\n", dirl, (char *)cbdata->filesspace + diroff);
 411 #endif
 412   if (!dirl || cbdata->filesspace[diroff] != '/')
 413     return diroff;
 414   /* strip / at end*/
 415   while (dirl && cbdata->filesspace[diroff + dirl - 1] == '/')
 416     dirl--;
 417   if (!dirl)
 418     return diroff;
 419
 420   /* find dirname */
 421   for (i = dirl - 1; i > 0; i--)
 422     if (cbdata->filesspace[diroff + i] == '/')
 423       break;
 424   i++;                          /* include trailing / */
 425
 426   /* normalize dirname */
 427   dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, i, strnhash((char *)cbdata->filesspace + diroff, i), 1);
 428   if (dirnameid == -1)
 429     return diroff;              /* hit "in progress" marker, some cyclic link */
 430
 431   /* sanity check result */
 432   if (cbdata->filesspace[dirnameid] != '/')
 433     return diroff;              /* hmm */
 434   l = strlen((char *)cbdata->filesspace + dirnameid);
 435   if (l && cbdata->filesspace[dirnameid + l - 1] != '/')
 436     return diroff;              /* hmm */
 437
 438   /* special handling for "." and ".." basename */
 439   if (cbdata->filesspace[diroff + i] == '.')
 440     {
 441       if (dirl - i == 1)
 442         return dirnameid;
 443       if (dirl - i == 2 && cbdata->filesspace[diroff + i + 1] == '.')
 444         {
 445           if (l <= 2)
 446             return dirnameid;   /* we hit our root */
 447           for (i = l - 2; i > 0; i--)
 448             if (cbdata->filesspace[dirnameid + i] == '/')
 449               break;
 450           i++;  /* include trailing / */
 451           dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + dirnameid, i, strnhash((char *)cbdata->filesspace + dirnameid, i), 1);
 452           return dirnameid == -1 ? diroff : dirnameid;
 453         }
 454     }
 455
 456   /* append basename to normalized dirname */
 457   if (cbdata->rootdirl + l + dirl - i + 1 > cbdata->canonspacen)
 458     {
 459       cbdata->canonspacen = cbdata->rootdirl + l + dirl - i + 20;
 460       cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
 461       strcpy(cbdata->canonspace, cbdata->rootdir);
 462     }
 463   strcpy(cbdata->canonspace + cbdata->rootdirl, (char *)cbdata->filesspace + dirnameid);
 464   strncpy(cbdata->canonspace + cbdata->rootdirl + l, (char *)cbdata->filesspace + diroff + i, dirl - i);
 465   cbdata->canonspace[cbdata->rootdirl + l + dirl - i] = 0;
 466
 467 #if 0
 468   printf("stat()ing %s\n", cbdata->canonspace);
 469 #endif
 470   cbdata->statsmade++;
 471   if (lstat(cbdata->canonspace, &stb) != 0 || !S_ISLNK(stb.st_mode))
 472     {
 473       /* not a symlink or stat failed, have new canon entry */
 474       diroff = addfilesspace(cbdata, l + dirl - i + 2);
 475       strcpy((char *)cbdata->filesspace + diroff, cbdata->canonspace + cbdata->rootdirl);
 476       l += dirl - i;
 477       /* add trailing / */
 478       if (cbdata->filesspace[diroff + l - 1] != '/')
 479         {
 480           cbdata->filesspace[diroff + l++] = '/';
 481           cbdata->filesspace[diroff + l] = 0;
 482         }
 483       /* call normalizedir on new entry for unification purposes */
 484       dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, l, strnhash((char *)cbdata->filesspace + diroff, l), 1);
 485       return dirnameid == -1 ? diroff : dirnameid;
 486     }
 487   /* oh no, a symlink! follow */
 488   lo = cbdata->rootdirl + l + dirl - i + 1;
 489   if (lo + stb.st_size + 2 > cbdata->canonspacen)
 490     {
 491       cbdata->canonspacen = lo + stb.st_size + 20;
 492       cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
 493     }
 494   ll = readlink(cbdata->canonspace, cbdata->canonspace + lo, stb.st_size);
 495   if (ll < 0 || ll > stb.st_size)
 496     return diroff;              /* hmm */
 497   if (ll == 0)
 498     return dirnameid;           /* empty means current dir */
 499   if (cbdata->canonspace[lo + ll - 1] != '/')
 500     cbdata->canonspace[lo + ll++] = '/';        /* add trailing / */
 501   cbdata->canonspace[lo + ll] = 0;              /* zero terminate */
 502   if (cbdata->canonspace[lo] != '/')
 503     {
 504       /* relative link, concatenate to dirname */
 505       memmove(cbdata->canonspace + cbdata->rootdirl + l, cbdata->canonspace + lo, ll + 1);
 506       lo = cbdata->rootdirl;
 507       ll += l;
 508     }
 509   dirnameid = normalizedir(cbdata, cbdata->canonspace + lo, ll, strnhash(cbdata->canonspace + lo, ll), 1);
 510   return dirnameid == -1 ? diroff : dirnameid;
 511 }
 512
 513 /*
 514  * map a directory (containing a trailing /) into a number.
 515  * for unifywithstat this is the offset to the 16 byte stat result.
 516  * for unifywithcanon this is the offset to the normailzed dir.
 517  */
 518 static Id
 519 normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create)
 520 {
 521   Hashval h, hh;
 522   Id qx;
 523   Id nspaceoff;
 524   int mycnt;
 525
 526   if (!hx)
 527     hx = dirl + 1;
 528   h = hx & cbdata->normapn;
 529   hh = HASHCHAIN_START;
 530   for (;;)
 531     {
 532       qx = cbdata->normap[2 * h];
 533       if (!qx)
 534         break;
 535       if (qx == hx)
 536         {
 537           Id off = cbdata->normap[2 * h + 1];
 538           char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
 539           if (!strncmp(dp, dir, dirl) && dp[dirl] == 0)
 540             return cbdata->norq.elements[off + 1];
 541         }
 542       h = HASHCHAIN_NEXT(h, hh, cbdata->normapn);
 543     }
 544   if (!create)
 545     return 0;
 546   /* new dir. work. */
 547   if (dir >= (const char *)cbdata->filesspace && dir < (const char *)cbdata->filesspace + cbdata->filesspacen)
 548     {
 549       /* can happen when called from unifywithcanon */
 550       Id off = dir - (const char *)cbdata->filesspace;
 551       nspaceoff = addfilesspace(cbdata, dirl + 1);
 552       dir = (const char *)cbdata->filesspace + off;
 553     }
 554   else
 555     nspaceoff = addfilesspace(cbdata, dirl + 1);
 556   if (dirl)
 557     memcpy(cbdata->filesspace + nspaceoff, dir, dirl);
 558   cbdata->filesspace[nspaceoff + dirl] = 0;
 559   mycnt = cbdata->norq.count;
 560   queue_push2(&cbdata->norq, nspaceoff, -1);    /* -1: in progress */
 561   cbdata->normap[2 * h] = hx;
 562   cbdata->normap[2 * h + 1] = mycnt;
 563   if (++cbdata->normapused * 2 > cbdata->normapn)
 564     cbdata->normap = growhash(cbdata->normap, &cbdata->normapn);
 565   /* unify */
 566   if (cbdata->usestat)
 567     nspaceoff = unifywithstat(cbdata, nspaceoff, dirl);
 568   else
 569     nspaceoff = unifywithcanon(cbdata, nspaceoff, dirl);
 570   cbdata->norq.elements[mycnt + 1] = nspaceoff; /* patch in result */
 571 #if 0
 572   if (!cbdata->usestat)
 573     printf("%s normalized to %d: %s\n", cbdata->filesspace + cbdata->norq.elements[mycnt], nspaceoff, cbdata->filesspace + nspaceoff);
 574 #endif
 575   return nspaceoff;
 576 }
 577
 578 /* collect all candidates for cflmap entries marked as "multiple" */
 579 static void
 580 findfileconflicts_alias_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 581 {
 582   int isdir = S_ISDIR(info->mode);
 583   struct cbdata *cbdata = cbdatav;
 584   const char *dp;
 585   Id idx, dirid;
 586   Id hx, qx;
 587   Hashval h, hh;
 588
 589   idx = cbdata->idx;
 590
 591   if (!info->dirlen)
 592     return;
 593   dp = fn + info->dirlen;
 594   if (info->diridx != cbdata->lastdiridx)
 595     {
 596       cbdata->lastdiridx = info->diridx;
 597       cbdata->lastdirhash = 0;
 598     }
 599   dp = fn + info->dirlen;
 600   hx = strhash(dp);
 601   if (!hx)
 602     hx = strlen(fn) + 1;
 603
 604   h = hx & cbdata->cflmapn;
 605   hh = HASHCHAIN_START;
 606   for (;;)
 607     {
 608       qx = cbdata->cflmap[2 * h];
 609       if (!qx)
 610         break;
 611       if (qx == hx)
 612         break;
 613       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 614     }
 615   if (!qx || cbdata->cflmap[2 * h + 1] != -1)
 616     return;
 617   /* found entry marked as "multiple", recored as conflict candidate */
 618   if (!cbdata->lastdirhash)
 619     cbdata->lastdirhash = strnhash(fn, dp - fn);
 620   dirid = normalizedir(cbdata, fn, dp - fn, cbdata->lastdirhash, 1);
 621   queue_push2(&cbdata->lookat, hx, idx);
 622   queue_push2(&cbdata->lookat, cbdata->lastdirhash, isdir ? -dirid : dirid);
 623 }
 624
 625 /* turn (hx, idx, dhx, dirid) entries into (hx, idx, off, dirid) entries,
 626  * where off is an offset into the filespace block */
 627 static void
 628 findfileconflicts_expand_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
 629 {
 630   struct cbdata *cbdata = cbdatav;
 631   Id hx, dhx;
 632   Hashval h, hh;
 633   const char *dp;
 634   char md5padded[34];
 635   Id off, dirid;
 636   int i;
 637
 638   if (!info->dirlen)
 639     return;
 640   dp = fn + info->dirlen;
 641   if (info->diridx != cbdata->lastdiridx)
 642     {
 643       cbdata->lastdiridx = info->diridx;
 644       cbdata->lastdirhash = strnhash(fn, dp - fn);
 645       if (cbdata->aliases)
 646         cbdata->lastdiridxbad = MAPTST(&cbdata->fetchdirmap, cbdata->lastdirhash & cbdata->fetchdirmapn) ? 0 : 1;
 647     }
 648   if (cbdata->lastdiridxbad)
 649     return;
 650   if (cbdata->aliases)
 651     {
 652       hx = strhash(dp);
 653       dhx = cbdata->lastdirhash;
 654       dirid =  normalizedir(cbdata, fn, dp - fn, dhx, 0);
 655     }
 656   else
 657     {
 658       hx = cbdata->lastdirhash;
 659       hx = strhash_cont(dp, hx);
 660       dhx = dirid = 0;
 661     }
 662   if (!hx)
 663     hx = strlen(fn) + 1;
 664
 665   h = (hx ^ (dirid * 37)) & cbdata->fetchmapn;
 666   hh = HASHCHAIN_START;
 667   for (;;)
 668     {
 669       i = cbdata->fetchmap[h];
 670       if (!i)
 671         break;
 672       if (cbdata->lookat.elements[i - 1] == hx && cbdata->lookat.elements[i + 2] == dirid && cbdata->lookat.elements[i + 1] == dhx)
 673         {
 674           /* printf("%d, hx %x dhx %x dirid %d -> %s   %d %s %d\n", cbdata->idx, hx, dhx, dirid, fn, info->mode, info->digest, info->color); */
 675           strncpy(md5padded, info->digest, 32);
 676           md5padded[32] = 0;
 677           md5padded[33] = info->color;
 678           off = addfilesspace(cbdata, strlen(fn) + (34 + 1));
 679           memcpy(cbdata->filesspace + off, (unsigned char *)md5padded, 34);
 680           strcpy((char *)cbdata->filesspace + off + 34, fn);
 681           queue_push2(&cbdata->lookat, hx, cbdata->idx);
 682           queue_push2(&cbdata->lookat, off, dirid);
 683         }
 684       h = HASHCHAIN_NEXT(h, hh, cbdata->fetchmapn);
 685     }
 686 }
 687
 688 static int
 689 lookat_idx_cmp(const void *ap, const void *bp, void *dp)
 690 {
 691   const Id *a = ap, *b = bp;
 692   unsigned int ahx, bhx;
 693   if (a[1] - b[1] != 0)         /* idx */
 694     return a[1] - b[1];
 695   if (a[3] - b[3] != 0)         /* dirid */
 696     return a[3] - b[3];
 697   ahx = (unsigned int)a[0];     /* can be < 0 */
 698   bhx = (unsigned int)b[0];
 699   if (ahx != bhx)
 700     return ahx < bhx ? -1 : 1;
 701   ahx = (unsigned int)a[2];     /* dhx */
 702   bhx = (unsigned int)b[2];
 703   if (ahx != bhx)
 704     return ahx < bhx ? -1 : 1;
 705   return 0;
 706 }
 707
 708 static int
 709 lookat_hx_cmp(const void *ap, const void *bp, void *dp)
 710 {
 711   const Id *a = ap, *b = bp;
 712   unsigned int ahx, bhx;
 713   Id adirid, bdirid;
 714   ahx = (unsigned int)a[0];     /* can be < 0 */
 715   bhx = (unsigned int)b[0];
 716   if (ahx != bhx)
 717     return ahx < bhx ? -1 : 1;
 718   adirid = a[3] < 0 ? -a[3] : a[3];
 719   bdirid = b[3] < 0 ? -b[3] : b[3];
 720   if (adirid - bdirid != 0)     /* dirid */
 721     return adirid - bdirid;
 722   if (a[3] != b[3])
 723     return a[3] > 0 ? -1 : 1;   /* bring positive dirids to front */
 724   if (a[1] - b[1] != 0)         /* idx */
 725     return a[1] - b[1];
 726   ahx = (unsigned int)a[2];     /* dhx */
 727   bhx = (unsigned int)b[2];
 728   if (ahx != bhx)
 729     return ahx < bhx ? -1 : 1;
 730   return 0;
 731 }
 732
 733 static int
 734 conflicts_cmp(const void *ap, const void *bp, void *dp)
 735 {
 736   Pool *pool = dp;
 737   const Id *a = ap;
 738   const Id *b = bp;
 739   if (a[0] != b[0])     /* filename1 */
 740     return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
 741   if (a[3] != b[3])     /* filename2 */
 742     return strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3]));
 743   if (a[1] != b[1])     /* pkgid1 */
 744     return a[1] - b[1];
 745   if (a[4] != b[4])     /* pkgid2 */
 746     return a[4] - b[4];
 747   return 0;
 748 }
 749
 750 static void
 751 iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
 752 {
 753   Repodata *lastdata = 0;
 754   Id lastdirid = -1;
 755   Dataiterator di;
 756
 757   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 758   while (dataiterator_step(&di))
 759     {
 760       if (di.data == lastdata && di.kv.id == lastdirid)
 761         continue;
 762       lastdata = di.data;
 763       lastdirid = di.kv.id;
 764       cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
 765     }
 766   dataiterator_free(&di);
 767 }
 768
 769 /* before calling the expensive findfileconflicts_cb we check if any of
 770  * the files match. This only makes sense when cbdata->create is off.
 771  */
 772 static int
 773 precheck_solvable_files(struct cbdata *cbdata, Pool *pool, Id p)
 774 {
 775   Dataiterator di;
 776   Id hx, qx;
 777   Hashval h, hh;
 778   int found = 0;
 779   int aliases = cbdata->aliases;
 780   unsigned int lastdirid = -1;
 781   Hashval lastdirhash = 0;
 782   int lastdirlen = 0;
 783   int checkthisdir = 0;
 784   Repodata *lastrepodata = 0;
 785
 786   dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
 787   while (dataiterator_step(&di))
 788     {
 789       if (aliases)
 790         {
 791           /* hash just the basename */
 792           hx = strhash(di.kv.str);
 793           if (!hx)
 794             hx = strlen(di.kv.str) + 1;
 795         }
 796       else
 797         {
 798           /* hash the full path */
 799           if (di.data != lastrepodata || di.kv.id != lastdirid)
 800             {
 801               const char *dir;
 802               lastrepodata = di.data;
 803               lastdirid = di.kv.id;
 804               dir = repodata_dir2str(lastrepodata, lastdirid, "");
 805               lastdirlen = strlen(dir);
 806               lastdirhash = strhash(dir);
 807               checkthisdir =  isindirmap(cbdata, lastdirhash ? lastdirhash : lastdirlen + 1);
 808             }
 809           if (!checkthisdir)
 810             continue;
 811           hx = strhash_cont(di.kv.str, lastdirhash);
 812           if (!hx)
 813             hx = lastdirlen + strlen(di.kv.str) + 1;
 814         }
 815       h = hx & cbdata->cflmapn;
 816       hh = HASHCHAIN_START;
 817       for (;;)
 818         {
 819           qx = cbdata->cflmap[2 * h];
 820           if (!qx)
 821             break;
 822           if (qx == hx)
 823             {
 824               found = 1;
 825               break;
 826             }
 827           h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
 828         }
 829       if (found)
 830         break;
 831     }
 832   dataiterator_free(&di);
 833   return found;
 834 }
 835
 836
 837 /* pool_findfileconflicts: find file conflicts in a set of packages
 838  * input:
 839  *   - pkgs: list of packages to check
 840  *   - cutoff: packages after this are not checked against each other
 841  *             this is useful to ignore file conflicts in already installed packages
 842  *   - flags: see pool_fileconflicts.h
 843  *   - handle_cb, handle_cbdata: callback for rpm header fetches
 844  * output:
 845  *   - conflicts: list of conflicts
 846  *
 847  * This is designed for needing only little memory while still being reasonable fast.
 848  * We do this by hashing the file names and working with the 32bit hash values in the
 849  * first steps of the algorithm. A hash conflict is not a problem as it will just
 850  * lead to some unneeded extra work later on.
 851  */
 852
 853 int
 854 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
 855 {
 856   int i, j, idxmapset;
 857   struct cbdata cbdata;
 858   unsigned int now, start;
 859   void *handle;
 860   Repo *installed = pool->installed;
 861   Id p;
 862   int usefilecolors;
 863   int hdrfetches;
 864   int lookat_cnt;
 865
 866   queue_empty(conflicts);
 867   if (!pkgs->count)
 868     return 0;
 869
 870   now = start = solv_timems(0);
 871   /* Hmm, should we have a different flag for this? */
 872   usefilecolors = pool_get_flag(pool, POOL_FLAG_IMPLICITOBSOLETEUSESCOLORS);
 873   POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
 874   POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d, usefilecolors %d\n", pkgs->count, cutoff, usefilecolors);
 875
 876   memset(&cbdata, 0, sizeof(cbdata));
 877   cbdata.aliases = flags & FINDFILECONFLICTS_CHECK_DIRALIASING;
 878   cbdata.pool = pool;
 879   if (cbdata.aliases && (flags & FINDFILECONFLICTS_USE_ROOTDIR) != 0)
 880     {
 881       cbdata.rootdir = pool_get_rootdir(pool);
 882       if (cbdata.rootdir && !strcmp(cbdata.rootdir, "/"))
 883         cbdata.rootdir = 0;
 884       if (cbdata.rootdir)
 885         cbdata.rootdirl = strlen(cbdata.rootdir);
 886       if (!cbdata.rootdir)
 887         cbdata.usestat = 1;
 888     }
 889   queue_init(&cbdata.lookat);
 890   queue_init(&cbdata.lookat_dir);
 891   map_init(&cbdata.idxmap, pkgs->count);
 892
 893   if (cutoff <= 0)
 894     cutoff = pkgs->count;
 895
 896   /* avarage file list size: 200 files per package */
 897   /* avarage dir count: 20 dirs per package */
 898
 899   /* first pass: find dirs belonging to multiple packages */
 900   if (!cbdata.aliases)
 901     {
 902       hdrfetches = 0;
 903       cbdata.dirmapn = mkmask((cutoff + 3) * 16);
 904       cbdata.dirmap = solv_calloc(cbdata.dirmapn + 1, 2 * sizeof(Id));
 905       cbdata.create = 1;
 906       idxmapset = 0;
 907       for (i = 0; i < pkgs->count; i++)
 908         {
 909           if (i == cutoff)
 910             cbdata.create = 0;
 911           cbdata.idx = i;
 912           p = pkgs->elements[i];
 913           if ((flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
 914             {
 915               if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
 916                 {
 917                   iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
 918                   if (MAPTST(&cbdata.idxmap, i))
 919                     idxmapset++;
 920                   continue;
 921                 }
 922             }
 923           handle = (*handle_cb)(pool, p, handle_cbdata);
 924           if (!handle)
 925             continue;
 926           hdrfetches++;
 927           rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
 928           if (MAPTST(&cbdata.idxmap, i))
 929             idxmapset++;
 930         }
 931       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
 932       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 933       POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
 934       POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
 935       POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
 936     }
 937
 938   /* second pass: scan files in the directories found above */
 939   now = solv_timems(0);
 940   cbdata.cflmapn = mkmask((cutoff + 3) * 32);
 941   cbdata.cflmap = solv_calloc(cbdata.cflmapn + 1, 2 * sizeof(Id));
 942   cbdata.create = 1;
 943   hdrfetches = 0;
 944   for (i = 0; i < pkgs->count; i++)
 945     {
 946       if (i == cutoff)
 947         cbdata.create = 0;
 948       if (!cbdata.aliases && !MAPTST(&cbdata.idxmap, i))
 949         continue;
 950       cbdata.idx = i;
 951       p = pkgs->elements[i];
 952       if (!cbdata.create && (flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
 953         {
 954           if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
 955             if (!precheck_solvable_files(&cbdata, pool, p))
 956               continue;
 957         }
 958       /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
 959        * the file is a directory or not */
 960       handle = (*handle_cb)(pool, p, handle_cbdata);
 961       if (!handle)
 962         continue;
 963       hdrfetches++;
 964       cbdata.lastdiridx = -1;
 965       rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, cbdata.aliases ? findfileconflicts_basename_cb : findfileconflicts_cb, &cbdata);
 966     }
 967
 968   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
 969   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
 970   POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
 971   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
 972   POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
 973   queue_free(&cbdata.lookat_dir);
 974
 975   /* we need another pass for aliases to generate the normalized directory ids */
 976   queue_init(&cbdata.norq);
 977   if (cbdata.aliases)
 978     {
 979       now = solv_timems(0);
 980       addfilesspace(&cbdata, 1);        /* make sure the first offset is not zero */
 981       cbdata.normapn = mkmask((cutoff + 3) * 4);
 982       cbdata.normap = solv_calloc(cbdata.normapn + 1, 2 * sizeof(Id));
 983       if (cbdata.usestat)
 984         {
 985           cbdata.statmapn = cbdata.normapn;
 986           cbdata.statmap = solv_calloc(cbdata.statmapn + 1, 2 * sizeof(Id));
 987         }
 988       cbdata.create = 0;
 989       hdrfetches = 0;
 990       for (i = 0; i < pkgs->count; i++)
 991         {
 992           if (!MAPTST(&cbdata.idxmap, i))
 993             continue;
 994           p = pkgs->elements[i];
 995           cbdata.idx = i;
 996           /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
 997            * the file is a directory or not */
 998           handle = (*handle_cb)(pool, p, handle_cbdata);
 999           if (!handle)
1000             continue;
1001           hdrfetches++;
1002           cbdata.lastdiridx = -1;
1003           rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_alias_cb, &cbdata);
1004         }
1005       POOL_DEBUG(SOLV_DEBUG_STATS, "normap size: %d, used %d\n", cbdata.normapn + 1, cbdata.normapused);
1006       POOL_DEBUG(SOLV_DEBUG_STATS, "normap memory usage: %d K\n", (cbdata.normapn + 1) * 2 * (int)sizeof(Id) / 1024);
1007       POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
1008       POOL_DEBUG(SOLV_DEBUG_STATS, "stats made: %d\n", cbdata.statsmade);
1009       if (cbdata.usestat)
1010         {
1011           POOL_DEBUG(SOLV_DEBUG_STATS, "statmap size: %d, used %d\n", cbdata.statmapn + 1, cbdata.statmapused);
1012           POOL_DEBUG(SOLV_DEBUG_STATS, "statmap memory usage: %d K\n", (cbdata.statmapn + 1) * 2 * (int)sizeof(Id) / 1024);
1013         }
1014       cbdata.statmap = solv_free(cbdata.statmap);
1015       cbdata.statmapn = 0;
1016       cbdata.canonspace = solv_free(cbdata.canonspace);
1017       cbdata.canonspacen = 0;
1018       POOL_DEBUG(SOLV_DEBUG_STATS, "alias processing took %d ms\n", solv_timems(now));
1019     }
1020
1021   /* free no longer used stuff */
1022   cbdata.dirmap = solv_free(cbdata.dirmap);
1023   cbdata.dirmapn = 0;
1024   cbdata.dirmapused = 0;
1025   cbdata.cflmap = solv_free(cbdata.cflmap);
1026   cbdata.cflmapn = 0;
1027   cbdata.cflmapused = 0;
1028   map_free(&cbdata.idxmap);
1029
1030   /* sort and unify/prune */
1031   /* this also makes all dirids positive as side effect */
1032   now = solv_timems(0);
1033   POOL_DEBUG(SOLV_DEBUG_STATS, "raw candidates: %d\n", cbdata.lookat.count / 4);
1034   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
1035   for (i = j = 0; i < cbdata.lookat.count; )
1036     {
1037       int first = 1, jstart = j;
1038       Id hx = cbdata.lookat.elements[i];
1039       Id idx = cbdata.lookat.elements[i + 1];
1040       Id dhx = cbdata.lookat.elements[i + 2];
1041       Id dirid = cbdata.lookat.elements[i + 3];
1042       i += 4;
1043       for (; i < cbdata.lookat.count && hx == cbdata.lookat.elements[i] && (dirid == cbdata.lookat.elements[i + 3] || dirid == -cbdata.lookat.elements[i + 3]); i += 4)
1044         {
1045           if (idx == cbdata.lookat.elements[i + 1] && dhx == cbdata.lookat.elements[i + 2])
1046             {
1047               if (first && idx < cutoff && cbdata.aliases && dirid >= 0)
1048                 first = 0;      /* special self-conflict case with dhx hash collision, e.g. /foo/xx and /fpf/xx */
1049               else
1050                 continue;       /* ignore duplicates */
1051             }
1052           if (first)
1053             {
1054               if (dirid < 0)
1055                 continue;       /* all have a neg dirid */
1056               cbdata.lookat.elements[j++] = hx;
1057               cbdata.lookat.elements[j++] = idx;
1058               cbdata.lookat.elements[j++] = dhx;
1059               cbdata.lookat.elements[j++] = dirid;
1060               first = 0;
1061               if (jstart >= 0 && idx < cutoff)
1062                 jstart = -1;
1063             }
1064           idx = cbdata.lookat.elements[i + 1];
1065           dhx = cbdata.lookat.elements[i + 2];
1066           cbdata.lookat.elements[j++] = hx;
1067           cbdata.lookat.elements[j++] = idx;
1068           cbdata.lookat.elements[j++] = dhx;
1069           cbdata.lookat.elements[j++] = dirid;
1070           if (jstart >= 0 && idx < cutoff)
1071             jstart = -1;
1072         }
1073       if (jstart >= 0)  /* we need at least one new candidate */
1074         j = jstart;
1075     }
1076   queue_truncate(&cbdata.lookat, j);
1077   POOL_DEBUG(SOLV_DEBUG_STATS, "pruned candidates: %d\n", cbdata.lookat.count / 4);
1078   POOL_DEBUG(SOLV_DEBUG_STATS, "pruning took %d ms\n", solv_timems(now));
1079
1080   /* third pass: expand to real file names */
1081   now = solv_timems(0);
1082   /* sort by idx so we can do all files of a package in one go */
1083   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_idx_cmp, pool);
1084   hdrfetches = 0;
1085   queue_init(&cbdata.newlookat);
1086   if (cbdata.lookat.count)
1087     {
1088       /* setup fetch map space */
1089       cbdata.fetchmapn = mkmask(cbdata.lookat.count + 3);
1090       if (cbdata.fetchmapn < 4095)
1091         cbdata.fetchmapn = 4095;
1092       cbdata.fetchmap = solv_calloc(cbdata.fetchmapn + 1, sizeof(Id));
1093       if (cbdata.aliases)
1094         {
1095           cbdata.fetchdirmapn = ((cbdata.fetchmapn + 1) / 16) - 1;
1096           map_init(&cbdata.fetchdirmap, cbdata.fetchdirmapn + 1);
1097         }
1098     }
1099   lookat_cnt = cbdata.lookat.count;
1100   while (lookat_cnt)
1101     {
1102       Id idx = cbdata.lookat.elements[1];
1103       int iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
1104       if (usefilecolors)
1105         iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
1106       /* find end of idx block */
1107       for (j = 4; j < lookat_cnt; j += 4)
1108         if (cbdata.lookat.elements[j + 1] != idx)
1109           break;
1110       p = pkgs->elements[idx];
1111       handle = (*handle_cb)(pool, p, handle_cbdata);
1112       if (!handle)
1113         {
1114           queue_deleten(&cbdata.lookat, 0, j);
1115           lookat_cnt -= j;
1116           continue;
1117         }
1118       hdrfetches++;
1119       /* create hash which maps (hx, dirid) to lookat elements */
1120       /* also create map from dhx values for fast reject */
1121       for (i = 0; i < j; i += 4)
1122         {
1123           Hashval h, hh;
1124           h = (cbdata.lookat.elements[i] ^ (cbdata.lookat.elements[i + 3] * 37)) & cbdata.fetchmapn;
1125           hh = HASHCHAIN_START;
1126           while (cbdata.fetchmap[h])
1127             h = HASHCHAIN_NEXT(h, hh, cbdata.fetchmapn);
1128           cbdata.fetchmap[h] = i + 1;
1129           cbdata.lookat.elements[i + 1] = (Id)h;        /* hack: misuse idx for easy hash cleanup */
1130           if (cbdata.fetchdirmapn)
1131             MAPSET(&cbdata.fetchdirmap, cbdata.lookat.elements[i + 2] & cbdata.fetchdirmapn);
1132         }
1133       cbdata.idx = idx;
1134       cbdata.lastdiridx = -1;
1135       cbdata.lastdiridxbad = 0;
1136       queue_prealloc(&cbdata.newlookat, j + 256);
1137       rpm_iterate_filelist(handle, iterflags, findfileconflicts_expand_cb, &cbdata);
1138       /* clear hash and map again */
1139       for (i = 0; i < j; i += 4)
1140         {
1141           Hashval h = (Hashval)cbdata.lookat.elements[i + 1];
1142           cbdata.fetchmap[h] = 0;
1143           if (cbdata.fetchdirmapn)
1144             MAPCLR_AT(&cbdata.fetchdirmap, cbdata.lookat.elements[i + 2] & cbdata.fetchdirmapn);
1145         }
1146       /* now delete old block and add new block to the end */
1147       queue_deleten(&cbdata.lookat, 0, j);
1148       queue_insertn(&cbdata.lookat, cbdata.lookat.count, cbdata.newlookat.count, cbdata.newlookat.elements);
1149       queue_empty(&cbdata.newlookat);
1150       lookat_cnt -= j;
1151     }
1152   queue_free(&cbdata.newlookat);
1153   POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
1154   POOL_DEBUG(SOLV_DEBUG_STATS, "candidates now: %d\n", cbdata.lookat.count / 4);
1155   POOL_DEBUG(SOLV_DEBUG_STATS, "file expansion took %d ms\n", solv_timems(now));
1156   /* free memory */
1157   cbdata.fetchmap = solv_free(cbdata.fetchmap);
1158   cbdata.fetchmapn = 0;
1159   if (cbdata.fetchdirmapn)
1160     map_free(&cbdata.fetchdirmap);
1161   cbdata.fetchdirmapn = 0;
1162   cbdata.normap = solv_free(cbdata.normap);
1163   cbdata.normapn = 0;
1164   queue_free(&cbdata.norq);
1165
1166   /* forth pass: for each (hx,dirid) we have, compare all matching files against all other matching files */
1167   now = solv_timems(0);
1168   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
1169   for (i = 0; i < cbdata.lookat.count - 4; i += 4)
1170     {
1171       Id hx = cbdata.lookat.elements[i];
1172       Id dirid = cbdata.lookat.elements[i + 3];
1173       Id idxi = cbdata.lookat.elements[i + 1];
1174       Id offi = cbdata.lookat.elements[i + 2];
1175       if (idxi >= cutoff)
1176         continue;       /* no conflicts between packages with idx >= cutoff */
1177       for (j = i + 4; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx && cbdata.lookat.elements[j + 3] == dirid; j += 4)
1178         {
1179           Id idxj = cbdata.lookat.elements[j + 1];
1180           Id offj = cbdata.lookat.elements[j + 2];
1181           char *fsi = (char *)cbdata.filesspace + offi;
1182           char *fsj = (char *)cbdata.filesspace + offj;
1183           if (cbdata.aliases)
1184             {
1185               /* compare just the basenames, the dirs match because of the dirid */
1186               char *bsi = strrchr(fsi + 34, '/');
1187               char *bsj = strrchr(fsj + 34, '/');
1188               if (!bsi || !bsj)
1189                 continue;
1190               if (strcmp(bsi, bsj))
1191                 continue;       /* different base names */
1192             }
1193           else
1194             {
1195               if (strcmp(fsi + 34, fsj + 34))
1196                 continue;       /* different file names */
1197             }
1198           if (!strcmp(fsi, fsj))
1199             continue;   /* file digests match, no conflict */
1200           if (usefilecolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
1201             continue;   /* colors do not conflict */
1202           queue_push(conflicts, pool_str2id(pool, fsi + 34, 1));
1203           queue_push(conflicts, pkgs->elements[idxi]);
1204           queue_push(conflicts, pool_str2id(pool, fsi, 1));
1205           queue_push(conflicts, pool_str2id(pool, fsj + 34, 1));
1206           queue_push(conflicts, pkgs->elements[idxj]);
1207           queue_push(conflicts, pool_str2id(pool, fsj, 1));
1208         }
1209     }
1210   POOL_DEBUG(SOLV_DEBUG_STATS, "filespace size: %d K\n", cbdata.filesspacen / 1024);
1211   POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
1212   cbdata.filesspace = solv_free(cbdata.filesspace);
1213   cbdata.filesspacen = 0;
1214   queue_free(&cbdata.lookat);
1215   if (conflicts->count > 6)
1216     solv_sort(conflicts->elements, conflicts->count / 6, 6 * sizeof(Id), conflicts_cmp, pool);
1217   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 6);
1218   POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
1219
1220   return conflicts->count / 6;
1221 }
1222