libsolv/ext/pool_fileconflicts.c

/*
 * Copyright (c) 2009-2013, Novell Inc.
 *
 * This program is licensed under the BSD license, read LICENSE.BSD
 * for further information
 */

#include <stdio.h>
#include <sys/stat.h>
#include <unistd.h>

#include "pool.h"
#include "repo.h"
#include "hash.h"
#include "repo_rpmdb.h"
#include "pool_fileconflicts.h"

struct cbdata {
  Pool *pool;
  int create;
  int aliases;

  Queue lookat;		/* conflict candidates */
  Queue lookat_dir;	/* not yet conflicting directories */

  Hashtable cflmap;
  Hashval cflmapn;
  unsigned int cflmapused;

  Hashtable dirmap;
  Hashval dirmapn;
  unsigned int dirmapused;
  int dirconflicts;

  Map idxmap;

  unsigned int lastdiridx;	/* last diridx we have seen */
  unsigned int lastdirhash;	/* strhash of last dir we have seen */
  int lastdiridxbad;

  Id idx;	/* index of package we're looking at */

  unsigned char *filesspace;
  unsigned int filesspacen;

  Hashtable normap;
  Hashval normapn;
  unsigned int normapused;
  Queue norq;

  Hashtable statmap;
  Hashval statmapn;
  unsigned int statmapused;

  int usestat;
  int statsmade;

  const char *rootdir;
  int rootdirl;

  char *canonspace;
  int canonspacen;

  Hashtable fetchmap;
  Hashval fetchmapn;
  Map fetchdirmap;
  int fetchdirmapn;
  Queue newlookat;
};

#define FILESSPACE_BLOCK 255

static Hashtable
growhash(Hashtable map, Hashval *mapnp)
{
  Hashval mapn = *mapnp;
  Hashval newn = (mapn + 1) * 2 - 1;
  Hashval i, h, hh;
  Hashtable m;
  Id hx, qx;

  m = solv_calloc(newn + 1, 2 * sizeof(Id));
  for (i = 0; i <= mapn; i++)
    {
      hx = map[2 * i];
      if (!hx)
	continue;
      h = hx & newn;
      hh = HASHCHAIN_START;
      for (;;)
	{
	  qx = m[2 * h];
	  if (!qx)
	    break;
	  h = HASHCHAIN_NEXT(h, hh, newn);
	}
      m[2 * h] = hx;
      m[2 * h + 1] = map[2 * i + 1];
    }
  solv_free(map);
  *mapnp = newn;
  return m;
}

/* first pass for non-alias mode:
 * create hash (dhx, idx) of directories that may have conflicts.
 * also create map "ixdmap" of packages involved
 */
static void
finddirs_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
{
  struct cbdata *cbdata = cbdatav;
  Hashval h, hh;
  Id dhx, qx;
  Id oidx, idx = cbdata->idx;

  dhx = strhash(fn);
  if (!dhx)
    dhx = strlen(fn) + 1;	/* make sure dhx is not zero */
  h = dhx & cbdata->dirmapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      qx = cbdata->dirmap[2 * h];
      if (!qx)
	break;
      if (qx == dhx)
	break;
      h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
    }
  if (!qx)
    {
      /* a miss */
      if (!cbdata->create)
	return;
      cbdata->dirmap[2 * h] = dhx;
      cbdata->dirmap[2 * h + 1] = idx;
      if (++cbdata->dirmapused * 2 > cbdata->dirmapn)
	cbdata->dirmap = growhash(cbdata->dirmap, &cbdata->dirmapn);
      return;
    }
  /* we saw this dir before */
  oidx = cbdata->dirmap[2 * h + 1];
  if (oidx == idx)
    return;
  /* found a conflict, this dir may be used in multiple packages */
  if (oidx != -1)
    {
      MAPSET(&cbdata->idxmap, oidx);
      cbdata->dirmap[2 * h + 1] = -1;	/* mark as "multiple packages" */
      cbdata->dirconflicts++;
    }
  MAPSET(&cbdata->idxmap, idx);
}

/* check if a dhx value is marked as "multiple" in the dirmap created by finddirs_cb */
static inline int
isindirmap(struct cbdata *cbdata, Id dhx)
{
  Hashval h, hh;
  Id qx;

  h = dhx & cbdata->dirmapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      qx = cbdata->dirmap[2 * h];
      if (!qx)
	return 0;
      if (qx == dhx)
	return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
      h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
    }
}

/* collect all possible file conflicts candidates in cbdata->lookat */
/* algorithm: hash file name into hx. Use cflmap the check if we have seen
 * this value before. If yes, we have a file conflict candidate. */
/* we also do extra work to ignore all-directory conflicts */
static void
findfileconflicts_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
{
  struct cbdata *cbdata = cbdatav;
  int isdir = S_ISDIR(info->mode);
  const char *dp;
  Id idx, oidx;
  Id hx, qx;
  Hashval h, hh, dhx;

  idx = cbdata->idx;

  if (!info->dirlen)
    return;
  dp = fn + info->dirlen;
  if (info->diridx != cbdata->lastdiridx)
    {
      cbdata->lastdiridx = info->diridx;
      cbdata->lastdirhash = strnhash(fn, dp - fn);
    }
  dhx = cbdata->lastdirhash;

  /* check if the directory is marked as "multiple" in the dirmap */
  /* this mirrors the "if (!dhx) dhx = strlen(fn) + 1" used in  finddirs_cb */
  if (!isindirmap(cbdata, dhx ? dhx : dp - fn + 1))
    return;

  hx = strhash_cont(dp, dhx);	/* extend hash to complete file name */
  if (!hx)
    hx = strlen(fn) + 1;	/* make sure hx is not zero */

  h = hx & cbdata->cflmapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      qx = cbdata->cflmap[2 * h];
      if (!qx)
	break;
      if (qx == hx)
	break;
      h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
    }
  if (!qx)
    {
      /* a miss */
      if (!cbdata->create)
	return;
      cbdata->cflmap[2 * h] = hx;
      cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
      if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
	cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
      return;
    }
  /* we have seen this hx before */
  oidx = cbdata->cflmap[2 * h + 1];
  if (oidx < 0)
    {
      int i;
      if (isdir)
	{
	  /* both are directories. delay the conflict, keep oidx in slot */
          queue_push2(&cbdata->lookat_dir, hx, idx);
	  return;
	}
      oidx = ~oidx;
      /* now have file, had directories before. */
      cbdata->cflmap[2 * h + 1] = oidx;	/* make it a file */
      /* dump all delayed directory hits for hx */
      for (i = 0; i < cbdata->lookat_dir.count; i += 2)
	if (cbdata->lookat_dir.elements[i] == hx)
	  {
	    queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
	    queue_push2(&cbdata->lookat, 0, 0);
	  }
    }
  else if (oidx == idx)
    return;	/* no conflicts with ourself, please */
  queue_push2(&cbdata->lookat, hx, oidx);
  queue_push2(&cbdata->lookat, 0, 0);
  queue_push2(&cbdata->lookat, hx, idx);
  queue_push2(&cbdata->lookat, 0, 0);
}

/* same as findfileconflicts_cb, but
 * - hashes with just the basename
 * - sets idx in a map instead of pushing to lookat
 * - sets the hash element to -1 ("multiple") if there may be a conflict
 * we then use findfileconflicts_alias_cb as second step to generate the candidates.
 * we do it this way because normailzing file names is expensive and thus we
 * only want to do it for entries marked as "multiple"
 */
static void
findfileconflicts_basename_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
{
  struct cbdata *cbdata = cbdatav;
  int isdir = S_ISDIR(info->mode);
  const char *dp;
  Id idx, oidx;
  Id hx, qx;
  Hashval h, hh;

  idx = cbdata->idx;

  if (!info->dirlen)
    return;
  dp = fn + info->dirlen;
  hx = strhash(dp);
  if (!hx)
    hx = strlen(fn) + 1;

  h = hx & cbdata->cflmapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      qx = cbdata->cflmap[2 * h];
      if (!qx)
	break;
      if (qx == hx)
	break;
      h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
    }
  if (!qx)
    {
      /* a miss */
      if (!cbdata->create)
	return;
      cbdata->cflmap[2 * h] = hx;
      cbdata->cflmap[2 * h + 1] = (isdir ? -idx - 2 : idx);
      if (++cbdata->cflmapused * 2 > cbdata->cflmapn)
	cbdata->cflmap = growhash(cbdata->cflmap, &cbdata->cflmapn);
      return;
    }
  oidx = cbdata->cflmap[2 * h + 1];
  if (oidx < -1)
    {
      int i;
      if (isdir)
	{
	  /* both are directories. delay the conflict, keep oidx in slot */
          queue_push2(&cbdata->lookat_dir, hx, idx);
	  return;
	}
      oidx = -idx - 2;
      /* now have file, had directories before. */
      cbdata->cflmap[2 * h + 1] = oidx;	/* make it a file */
      /* dump all delayed directory hits for hx */
      for (i = 0; i < cbdata->lookat_dir.count; i += 2)
	if (cbdata->lookat_dir.elements[i] == hx)
	  MAPSET(&cbdata->idxmap, cbdata->lookat_dir.elements[i + 1]);
    }
  else if (oidx == idx)
    return;	/* no conflicts with ourself, please */
  if (oidx >= 0)
    MAPSET(&cbdata->idxmap, oidx);
  MAPSET(&cbdata->idxmap, idx);
  if (oidx != -1)
    cbdata->cflmap[2 * h + 1] = -1;
}

static inline Id
addfilesspace(struct cbdata *cbdata, int len)
{
  unsigned int off = cbdata->filesspacen;
  cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
  cbdata->filesspacen += len;
  return off;
}

static Id
unifywithstat(struct cbdata *cbdata, Id diroff, int dirl)
{
  struct stat stb;
  int i;
  Hashval h, hh;
  Id hx, qx;
  Id nspaceoff;
  unsigned char statdata[16 + sizeof(stb.st_dev) + sizeof(stb.st_ino)];

  if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == '/')
    cbdata->filesspace[diroff + dirl - 1] = 0;
  cbdata->statsmade++;
  i = stat((char *)cbdata->filesspace + diroff, &stb);
  if (dirl > 1 && cbdata->filesspace[diroff + dirl - 1] == 0)
    cbdata->filesspace[diroff + dirl - 1] = '/';
  if (i)
    return diroff;
  memset(statdata, 0, 16);
  memcpy(statdata + 8, &stb.st_dev, sizeof(stb.st_dev));
  memcpy(statdata, &stb.st_ino, sizeof(stb.st_ino));
  hx = 0;
  for (i = 15; i >= 0; i--)
    hx = (unsigned int)hx * 13 + statdata[i];
  h = hx & cbdata->statmapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      qx = cbdata->statmap[2 * h];
      if (!qx)
	break;
      if (qx == hx)
	{
	  Id off = cbdata->statmap[2 * h + 1];
	  char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
	  if (!memcmp(dp, statdata, 16))
	    return cbdata->norq.elements[off + 1];
	}
      h = HASHCHAIN_NEXT(h, hh, cbdata->statmapn);
    }
  /* new stat result. work. */
  nspaceoff = addfilesspace(cbdata, 16);
  memcpy(cbdata->filesspace + nspaceoff, statdata, 16);
  queue_push2(&cbdata->norq, nspaceoff, nspaceoff);
  cbdata->statmap[2 * h] = hx;
  cbdata->statmap[2 * h + 1] = cbdata->norq.count - 2;
  if (++cbdata->statmapused * 2 > cbdata->statmapn)
    cbdata->statmap = growhash(cbdata->statmap, &cbdata->statmapn);
  return nspaceoff;
}

/* forward declaration */
static Id normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create);

static Id
unifywithcanon(struct cbdata *cbdata, Id diroff, int dirl)
{
  Id dirnameid;
  int i, l, ll, lo;
  struct stat stb;

#if 0
  printf("UNIFY %.*s\n", dirl, (char *)cbdata->filesspace + diroff);
#endif
  if (!dirl || cbdata->filesspace[diroff] != '/')
    return diroff;
  /* strip / at end*/
  while (dirl && cbdata->filesspace[diroff + dirl - 1] == '/')
    dirl--;
  if (!dirl)
    return diroff;

  /* find dirname */
  for (i = dirl - 1; i > 0; i--)
    if (cbdata->filesspace[diroff + i] == '/')
      break;
  i++;				/* include trailing / */

  /* normalize dirname */
  dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, i, strnhash((char *)cbdata->filesspace + diroff, i), 1);
  if (dirnameid == -1)
    return diroff;		/* hit "in progress" marker, some cyclic link */

  /* sanity check result */
  if (cbdata->filesspace[dirnameid] != '/')
    return diroff;		/* hmm */
  l = strlen((char *)cbdata->filesspace + dirnameid);
  if (l && cbdata->filesspace[dirnameid + l - 1] != '/')
    return diroff;		/* hmm */

  /* special handling for "." and ".." basename */
  if (cbdata->filesspace[diroff + i] == '.')
    {
      if (dirl - i == 1)
	return dirnameid;
      if (dirl - i == 2 && cbdata->filesspace[diroff + i + 1] == '.')
	{
	  if (l <= 2)
	    return dirnameid;	/* we hit our root */
	  for (i = l - 2; i > 0; i--)
	    if (cbdata->filesspace[dirnameid + i] == '/')
	      break;
	  i++;	/* include trailing / */
	  dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + dirnameid, i, strnhash((char *)cbdata->filesspace + dirnameid, i), 1);
	  return dirnameid == -1 ? diroff : dirnameid;
	}
    }

  /* append basename to normalized dirname */
  if (cbdata->rootdirl + l + dirl - i + 1 > cbdata->canonspacen)
    {
      cbdata->canonspacen = cbdata->rootdirl + l + dirl - i + 20;
      cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
      strcpy(cbdata->canonspace, cbdata->rootdir);
    }
  strcpy(cbdata->canonspace + cbdata->rootdirl, (char *)cbdata->filesspace + dirnameid);
  strncpy(cbdata->canonspace + cbdata->rootdirl + l, (char *)cbdata->filesspace + diroff + i, dirl - i);
  cbdata->canonspace[cbdata->rootdirl + l + dirl - i] = 0;

#if 0
  printf("stat()ing %s\n", cbdata->canonspace);
#endif
  cbdata->statsmade++;
  if (lstat(cbdata->canonspace, &stb) != 0 || !S_ISLNK(stb.st_mode))
    {
      /* not a symlink or stat failed, have new canon entry */
      diroff = addfilesspace(cbdata, l + dirl - i + 2);
      strcpy((char *)cbdata->filesspace + diroff, cbdata->canonspace + cbdata->rootdirl);
      l += dirl - i;
      /* add trailing / */
      if (cbdata->filesspace[diroff + l - 1] != '/')
	{
	  cbdata->filesspace[diroff + l++] = '/';
	  cbdata->filesspace[diroff + l] = 0;
	}
      /* call normalizedir on new entry for unification purposes */
      dirnameid = normalizedir(cbdata, (char *)cbdata->filesspace + diroff, l, strnhash((char *)cbdata->filesspace + diroff, l), 1);
      return dirnameid == -1 ? diroff : dirnameid;
    }
  /* oh no, a symlink! follow */
  lo = cbdata->rootdirl + l + dirl - i + 1;
  if (lo + stb.st_size + 2 > cbdata->canonspacen)
    {
      cbdata->canonspacen = lo + stb.st_size + 20;
      cbdata->canonspace = solv_realloc(cbdata->canonspace, cbdata->canonspacen);
    }
  ll = readlink(cbdata->canonspace, cbdata->canonspace + lo, stb.st_size);
  if (ll < 0 || ll > stb.st_size)
    return diroff;		/* hmm */
  if (ll == 0)
    return dirnameid;		/* empty means current dir */
  if (cbdata->canonspace[lo + ll - 1] != '/')
    cbdata->canonspace[lo + ll++] = '/';	/* add trailing / */
  cbdata->canonspace[lo + ll] = 0;		/* zero terminate */
  if (cbdata->canonspace[lo] != '/')
    {
      /* relative link, concatenate to dirname */
      memmove(cbdata->canonspace + cbdata->rootdirl + l, cbdata->canonspace + lo, ll + 1);
      lo = cbdata->rootdirl;
      ll += l;
    }
  dirnameid = normalizedir(cbdata, cbdata->canonspace + lo, ll, strnhash(cbdata->canonspace + lo, ll), 1);
  return dirnameid == -1 ? diroff : dirnameid;
}

/*
 * map a directory (containing a trailing /) into a number.
 * for unifywithstat this is the offset to the 16 byte stat result.
 * for unifywithcanon this is the offset to the normailzed dir.
 */
static Id
normalizedir(struct cbdata *cbdata, const char *dir, int dirl, Id hx, int create)
{
  Hashval h, hh;
  Id qx;
  Id nspaceoff;
  int mycnt;

  if (!hx)
    hx = dirl + 1;
  h = hx & cbdata->normapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      qx = cbdata->normap[2 * h];
      if (!qx)
	break;
      if (qx == hx)
	{
	  Id off = cbdata->normap[2 * h + 1];
	  char *dp = (char *)cbdata->filesspace + cbdata->norq.elements[off];
	  if (!strncmp(dp, dir, dirl) && dp[dirl] == 0)
	    return cbdata->norq.elements[off + 1];
	}
      h = HASHCHAIN_NEXT(h, hh, cbdata->normapn);
    }
  if (!create)
    return 0;
  /* new dir. work. */
  if (dir >= (const char *)cbdata->filesspace && dir < (const char *)cbdata->filesspace + cbdata->filesspacen)
    {
      /* can happen when called from unifywithcanon */
      Id off = dir - (const char *)cbdata->filesspace;
      nspaceoff = addfilesspace(cbdata, dirl + 1);
      dir = (const char *)cbdata->filesspace + off;
    }
  else
    nspaceoff = addfilesspace(cbdata, dirl + 1);
  if (dirl)
    memcpy(cbdata->filesspace + nspaceoff, dir, dirl);
  cbdata->filesspace[nspaceoff + dirl] = 0;
  mycnt = cbdata->norq.count;
  queue_push2(&cbdata->norq, nspaceoff, -1);	/* -1: in progress */
  cbdata->normap[2 * h] = hx;
  cbdata->normap[2 * h + 1] = mycnt;
  if (++cbdata->normapused * 2 > cbdata->normapn)
    cbdata->normap = growhash(cbdata->normap, &cbdata->normapn);
  /* unify */
  if (cbdata->usestat)
    nspaceoff = unifywithstat(cbdata, nspaceoff, dirl);
  else
    nspaceoff = unifywithcanon(cbdata, nspaceoff, dirl);
  cbdata->norq.elements[mycnt + 1] = nspaceoff;	/* patch in result */
#if 0
  if (!cbdata->usestat)
    printf("%s normalized to %d: %s\n", cbdata->filesspace + cbdata->norq.elements[mycnt], nspaceoff, cbdata->filesspace + nspaceoff);
#endif
  return nspaceoff;
}

/* collect all candidates for cflmap entries marked as "multiple" */
static void
findfileconflicts_alias_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
{
  int isdir = S_ISDIR(info->mode);
  struct cbdata *cbdata = cbdatav;
  const char *dp;
  Id idx, dirid;
  Id hx, qx;
  Hashval h, hh;

  idx = cbdata->idx;

  if (!info->dirlen)
    return;
  if (info->diridx != cbdata->lastdiridx)
    {
      cbdata->lastdiridx = info->diridx;
      cbdata->lastdirhash = 0;
    }
  dp = fn + info->dirlen;
  hx = strhash(dp);
  if (!hx)
    hx = strlen(fn) + 1;

  h = hx & cbdata->cflmapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      qx = cbdata->cflmap[2 * h];
      if (!qx)
	break;
      if (qx == hx)
	break;
      h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
    }
  if (!qx || cbdata->cflmap[2 * h + 1] != -1)
    return;
  /* found entry marked as "multiple", recored as conflict candidate */
  if (!cbdata->lastdirhash)
    cbdata->lastdirhash = strnhash(fn, dp - fn);
  dirid = normalizedir(cbdata, fn, dp - fn, cbdata->lastdirhash, 1);
  queue_push2(&cbdata->lookat, hx, idx);
  queue_push2(&cbdata->lookat, cbdata->lastdirhash, isdir ? -dirid : dirid);
}

/* turn (hx, idx, dhx, dirid) entries into (hx, idx, off, dirid) entries,
 * where off is an offset into the filespace block */
static void
findfileconflicts_expand_cb(void *cbdatav, const char *fn, struct filelistinfo *info)
{
  struct cbdata *cbdata = cbdatav;
  Id hx, dhx;
  Hashval h, hh;
  const char *dp;
  char md5padded[34];
  Id off, dirid;
  int i;

  if (!info->dirlen)
    return;
  dp = fn + info->dirlen;
  if (info->diridx != cbdata->lastdiridx)
    {
      cbdata->lastdiridx = info->diridx;
      cbdata->lastdirhash = strnhash(fn, dp - fn);
      if (cbdata->aliases)
        cbdata->lastdiridxbad = MAPTST(&cbdata->fetchdirmap, cbdata->lastdirhash & cbdata->fetchdirmapn) ? 0 : 1;
    }
  if (cbdata->lastdiridxbad)
    return;
  if (cbdata->aliases)
    {
      hx = strhash(dp);
      dhx = cbdata->lastdirhash;
      dirid =  normalizedir(cbdata, fn, dp - fn, dhx, 0);
    }
  else
    {
      hx = cbdata->lastdirhash;
      hx = strhash_cont(dp, hx);
      dhx = dirid = 0;
    }
  if (!hx)
    hx = strlen(fn) + 1;

  h = (hx ^ (dirid * 37)) & cbdata->fetchmapn;
  hh = HASHCHAIN_START;
  for (;;)
    {
      i = cbdata->fetchmap[h];
      if (!i)
	break;
      if (cbdata->lookat.elements[i - 1] == hx && cbdata->lookat.elements[i + 2] == dirid && cbdata->lookat.elements[i + 1] == dhx)
	{
          /* 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); */
	  strncpy(md5padded, info->digest, 32);
	  md5padded[32] = 0;
	  md5padded[33] = info->color;
	  off = addfilesspace(cbdata, strlen(fn) + (34 + 1));
	  memcpy(cbdata->filesspace + off, (unsigned char *)md5padded, 34);
          strcpy((char *)cbdata->filesspace + off + 34, fn);
	  queue_push2(&cbdata->lookat, hx, cbdata->idx);
	  queue_push2(&cbdata->lookat, off, dirid);
	}
      h = HASHCHAIN_NEXT(h, hh, cbdata->fetchmapn);
    }
}

static int
lookat_idx_cmp(const void *ap, const void *bp, void *dp)
{
  const Id *a = ap, *b = bp;
  unsigned int ahx, bhx;
  if (a[1] - b[1] != 0)		/* idx */
    return a[1] - b[1];
  if (a[3] - b[3] != 0)		/* dirid */
    return a[3] - b[3];
  ahx = (unsigned int)a[0];	/* can be < 0 */
  bhx = (unsigned int)b[0];
  if (ahx != bhx)
    return ahx < bhx ? -1 : 1;
  ahx = (unsigned int)a[2];	/* dhx */
  bhx = (unsigned int)b[2];
  if (ahx != bhx)
    return ahx < bhx ? -1 : 1;
  return 0;
}

static int
lookat_hx_cmp(const void *ap, const void *bp, void *dp)
{
  const Id *a = ap, *b = bp;
  unsigned int ahx, bhx;
  Id adirid, bdirid;
  ahx = (unsigned int)a[0];	/* can be < 0 */
  bhx = (unsigned int)b[0];
  if (ahx != bhx)
    return ahx < bhx ? -1 : 1;
  adirid = a[3] < 0 ? -a[3] : a[3];
  bdirid = b[3] < 0 ? -b[3] : b[3];
  if (adirid - bdirid != 0)	/* dirid */
    return adirid - bdirid;
  if (a[3] != b[3])
    return a[3] > 0 ? -1 : 1; 	/* bring positive dirids to front */
  if (a[1] - b[1] != 0)		/* idx */
    return a[1] - b[1];
  ahx = (unsigned int)a[2];	/* dhx */
  bhx = (unsigned int)b[2];
  if (ahx != bhx)
    return ahx < bhx ? -1 : 1;
  return 0;
}

static int
conflicts_cmp(const void *ap, const void *bp, void *dp)
{
  Pool *pool = dp;
  const Id *a = ap;
  const Id *b = bp;
  if (a[0] != b[0])	/* filename1 */
    return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
  if (a[3] != b[3])	/* filename2 */
    return strcmp(pool_id2str(pool, a[3]), pool_id2str(pool, b[3]));
  if (a[1] != b[1])	/* pkgid1 */
    return a[1] - b[1];
  if (a[4] != b[4])	/* pkgid2 */
    return a[4] - b[4];
  return 0;
}

static void
iterate_solvable_dirs(Pool *pool, Id p, void (*cb)(void *, const char *, struct filelistinfo *), void *cbdata)
{
  Repodata *lastdata = 0;
  Id lastdirid = -1;
  Dataiterator di;

  dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
  while (dataiterator_step(&di))
    {
      if (di.data == lastdata && di.kv.id == lastdirid)
	continue;
      lastdata = di.data;
      lastdirid = di.kv.id;
      cb(cbdata, repodata_dir2str(di.data, di.kv.id, ""), 0);
    }
  dataiterator_free(&di);
}

/* before calling the expensive findfileconflicts_cb we check if any of
 * the files match. This only makes sense when cbdata->create is off.
 */
static int
precheck_solvable_files(struct cbdata *cbdata, Pool *pool, Id p)
{
  Dataiterator di;
  Id hx, qx;
  Hashval h, hh;
  int found = 0;
  int aliases = cbdata->aliases;
  unsigned int lastdirid = -1;
  Hashval lastdirhash = 0;
  int lastdirlen = 0;
  int checkthisdir = 0;
  Repodata *lastrepodata = 0;

  dataiterator_init(&di, pool, 0, p, SOLVABLE_FILELIST, 0, SEARCH_COMPLETE_FILELIST);
  while (dataiterator_step(&di))
    {
      if (aliases)
	{
	  /* hash just the basename */
	  hx = strhash(di.kv.str);
	  if (!hx)
	    hx = strlen(di.kv.str) + 1;
	}
      else
	{
	  /* hash the full path */
	  if (di.data != lastrepodata || di.kv.id != lastdirid)
	    {
	      const char *dir;
	      lastrepodata = di.data;
	      lastdirid = di.kv.id;
	      dir = repodata_dir2str(lastrepodata, lastdirid, "");
	      lastdirlen = strlen(dir);
	      lastdirhash = strhash(dir);
	      checkthisdir =  isindirmap(cbdata, lastdirhash ? lastdirhash : lastdirlen + 1);
	    }
	  if (!checkthisdir)
	    continue;
	  hx = strhash_cont(di.kv.str, lastdirhash);
	  if (!hx)
	    hx = lastdirlen + strlen(di.kv.str) + 1;
	}
      h = hx & cbdata->cflmapn;
      hh = HASHCHAIN_START;
      for (;;)
	{
	  qx = cbdata->cflmap[2 * h];
	  if (!qx)
	    break;
	  if (qx == hx)
	    {
	      found = 1;
	      break;
	    }
	  h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
	}
      if (found)
	break;
    }
  dataiterator_free(&di);
  return found;
}


/* pool_findfileconflicts: find file conflicts in a set of packages
 * input:
 *   - pkgs: list of packages to check
 *   - cutoff: packages after this are not checked against each other
 *             this is useful to ignore file conflicts in already installed packages
 *   - flags: see pool_fileconflicts.h
 *   - handle_cb, handle_cbdata: callback for rpm header fetches
 * output:
 *   - conflicts: list of conflicts
 *
 * This is designed for needing only little memory while still being reasonable fast.
 * We do this by hashing the file names and working with the 32bit hash values in the
 * first steps of the algorithm. A hash conflict is not a problem as it will just
 * lead to some unneeded extra work later on.
 */

int
pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, int flags, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
{
  int i, j, idxmapset;
  struct cbdata cbdata;
  unsigned int now, start;
  void *handle;
  Repo *installed = pool->installed;
  Id p;
  int usefilecolors;
  int hdrfetches;
  int lookat_cnt;

  queue_empty(conflicts);
  if (!pkgs->count)
    return 0;

  now = start = solv_timems(0);
  /* Hmm, should we have a different flag for this? */
  usefilecolors = pool_get_flag(pool, POOL_FLAG_IMPLICITOBSOLETEUSESCOLORS);
  POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
  POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d, usefilecolors %d\n", pkgs->count, cutoff, usefilecolors);

  memset(&cbdata, 0, sizeof(cbdata));
  cbdata.aliases = flags & FINDFILECONFLICTS_CHECK_DIRALIASING;
  cbdata.pool = pool;
  if (cbdata.aliases && (flags & FINDFILECONFLICTS_USE_ROOTDIR) != 0)
    {
      cbdata.rootdir = pool_get_rootdir(pool);
      if (cbdata.rootdir && !strcmp(cbdata.rootdir, "/"))
	cbdata.rootdir = 0;
      if (cbdata.rootdir)
	cbdata.rootdirl = strlen(cbdata.rootdir);
      if (!cbdata.rootdir)
	cbdata.usestat = 1;
    }
  queue_init(&cbdata.lookat);
  queue_init(&cbdata.lookat_dir);
  map_init(&cbdata.idxmap, pkgs->count);

  if (cutoff <= 0)
    cutoff = pkgs->count;

  /* avarage file list size: 200 files per package */
  /* avarage dir count: 20 dirs per package */

  /* first pass: find dirs belonging to multiple packages */
  if (!cbdata.aliases)
    {
      hdrfetches = 0;
      cbdata.dirmapn = mkmask((cutoff + 3) * 16);
      cbdata.dirmap = solv_calloc(cbdata.dirmapn + 1, 2 * sizeof(Id));
      cbdata.create = 1;
      idxmapset = 0;
      for (i = 0; i < pkgs->count; i++)
	{
	  if (i == cutoff)
	    cbdata.create = 0;
	  cbdata.idx = i;
	  p = pkgs->elements[i];
	  if ((flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
	    {
	      if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
		{
		  iterate_solvable_dirs(pool, p, finddirs_cb, &cbdata);
		  if (MAPTST(&cbdata.idxmap, i))
		    idxmapset++;
		  continue;
		}
	    }
	  handle = (*handle_cb)(pool, p, handle_cbdata);
	  if (!handle)
	    continue;
	  hdrfetches++;
	  rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
	  if (MAPTST(&cbdata.idxmap, i))
	    idxmapset++;
	}
      POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d, used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
      POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
      POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
      POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
      POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
    }

  /* second pass: scan files in the directories found above */
  now = solv_timems(0);
  cbdata.cflmapn = mkmask((cutoff + 3) * 32);
  cbdata.cflmap = solv_calloc(cbdata.cflmapn + 1, 2 * sizeof(Id));
  cbdata.create = 1;
  hdrfetches = 0;
  for (i = 0; i < pkgs->count; i++)
    {
      if (i == cutoff)
	cbdata.create = 0;
      if (!cbdata.aliases && !MAPTST(&cbdata.idxmap, i))
	continue;
      cbdata.idx = i;
      p = pkgs->elements[i];
      if (!cbdata.create && (flags & FINDFILECONFLICTS_USE_SOLVABLEFILELIST) != 0 && installed)
	{
	  if (p >= installed->start && p < installed->end && pool->solvables[p].repo == installed)
	    if (!precheck_solvable_files(&cbdata, pool, p))
	      continue;
	}
      /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
       * the file is a directory or not */
      handle = (*handle_cb)(pool, p, handle_cbdata);
      if (!handle)
	continue;
      hdrfetches++;
      cbdata.lastdiridx = -1;
      rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, cbdata.aliases ? findfileconflicts_basename_cb : findfileconflicts_cb, &cbdata);
    }

  POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d, used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
  POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
  POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
  POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
  POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
  queue_free(&cbdata.lookat_dir);

  /* we need another pass for aliases to generate the normalized directory ids */
  queue_init(&cbdata.norq);
  if (cbdata.aliases)
    {
      now = solv_timems(0);
      addfilesspace(&cbdata, 1);	/* make sure the first offset is not zero */
      cbdata.normapn = mkmask((cutoff + 3) * 4);
      cbdata.normap = solv_calloc(cbdata.normapn + 1, 2 * sizeof(Id));
      if (cbdata.usestat)
	{
	  cbdata.statmapn = cbdata.normapn;
	  cbdata.statmap = solv_calloc(cbdata.statmapn + 1, 2 * sizeof(Id));
	}
      cbdata.create = 0;
      hdrfetches = 0;
      for (i = 0; i < pkgs->count; i++)
	{
	  if (!MAPTST(&cbdata.idxmap, i))
	    continue;
	  p = pkgs->elements[i];
	  cbdata.idx = i;
	  /* can't use FINDFILECONFLICTS_USE_SOLVABLEFILELIST because we have to know if
	   * the file is a directory or not */
	  handle = (*handle_cb)(pool, p, handle_cbdata);
	  if (!handle)
	    continue;
	  hdrfetches++;
	  cbdata.lastdiridx = -1;
	  rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_alias_cb, &cbdata);
	}
      POOL_DEBUG(SOLV_DEBUG_STATS, "normap size: %d, used %d\n", cbdata.normapn + 1, cbdata.normapused);
      POOL_DEBUG(SOLV_DEBUG_STATS, "normap memory usage: %d K\n", (cbdata.normapn + 1) * 2 * (int)sizeof(Id) / 1024);
      POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
      POOL_DEBUG(SOLV_DEBUG_STATS, "stats made: %d\n", cbdata.statsmade);
      if (cbdata.usestat)
	{
	  POOL_DEBUG(SOLV_DEBUG_STATS, "statmap size: %d, used %d\n", cbdata.statmapn + 1, cbdata.statmapused);
	  POOL_DEBUG(SOLV_DEBUG_STATS, "statmap memory usage: %d K\n", (cbdata.statmapn + 1) * 2 * (int)sizeof(Id) / 1024);
	}
      cbdata.statmap = solv_free(cbdata.statmap);
      cbdata.statmapn = 0;
      cbdata.canonspace = solv_free(cbdata.canonspace);
      cbdata.canonspacen = 0;
      POOL_DEBUG(SOLV_DEBUG_STATS, "alias processing took %d ms\n", solv_timems(now));
    }

  /* free no longer used stuff */
  cbdata.dirmap = solv_free(cbdata.dirmap);
  cbdata.dirmapn = 0;
  cbdata.dirmapused = 0;
  cbdata.cflmap = solv_free(cbdata.cflmap);
  cbdata.cflmapn = 0;
  cbdata.cflmapused = 0;
  map_free(&cbdata.idxmap);

  /* sort and unify/prune */
  /* this also makes all dirids positive as side effect */
  now = solv_timems(0);
  POOL_DEBUG(SOLV_DEBUG_STATS, "raw candidates: %d\n", cbdata.lookat.count / 4);
  solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
  for (i = j = 0; i < cbdata.lookat.count; )
    {
      int first = 1, jstart = j;
      Id hx = cbdata.lookat.elements[i];
      Id idx = cbdata.lookat.elements[i + 1];
      Id dhx = cbdata.lookat.elements[i + 2];
      Id dirid = cbdata.lookat.elements[i + 3];
      i += 4;
      for (; i < cbdata.lookat.count && hx == cbdata.lookat.elements[i] && (dirid == cbdata.lookat.elements[i + 3] || dirid == -cbdata.lookat.elements[i + 3]); i += 4)
	{
	  if (idx == cbdata.lookat.elements[i + 1] && dhx == cbdata.lookat.elements[i + 2])
	    {
	      if (first && idx < cutoff && cbdata.aliases && dirid >= 0)
		first = 0;	/* special self-conflict case with dhx hash collision, e.g. /foo/xx and /fpf/xx */
	      else
	        continue;	/* ignore duplicates */
	    }
	  if (first)
	    {
	      if (dirid < 0)
		continue;	/* all have a neg dirid */
	      cbdata.lookat.elements[j++] = hx;
	      cbdata.lookat.elements[j++] = idx;
	      cbdata.lookat.elements[j++] = dhx;
	      cbdata.lookat.elements[j++] = dirid;
	      first = 0;
	      if (jstart >= 0 && idx < cutoff)
		jstart = -1;
	    }
	  idx = cbdata.lookat.elements[i + 1];
	  dhx = cbdata.lookat.elements[i + 2];
	  cbdata.lookat.elements[j++] = hx;
	  cbdata.lookat.elements[j++] = idx;
	  cbdata.lookat.elements[j++] = dhx;
	  cbdata.lookat.elements[j++] = dirid;
	  if (jstart >= 0 && idx < cutoff)
	    jstart = -1;
	}
      if (jstart >= 0)	/* we need at least one new candidate */
	j = jstart;
    }
  queue_truncate(&cbdata.lookat, j);
  POOL_DEBUG(SOLV_DEBUG_STATS, "pruned candidates: %d\n", cbdata.lookat.count / 4);
  POOL_DEBUG(SOLV_DEBUG_STATS, "pruning took %d ms\n", solv_timems(now));

  /* third pass: expand to real file names */
  now = solv_timems(0);
  /* sort by idx so we can do all files of a package in one go */
  solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_idx_cmp, pool);
  hdrfetches = 0;
  queue_init(&cbdata.newlookat);
  if (cbdata.lookat.count)
    {
      /* setup fetch map space */
      cbdata.fetchmapn = mkmask(cbdata.lookat.count + 3);
      if (cbdata.fetchmapn < 4095)
        cbdata.fetchmapn = 4095;
      cbdata.fetchmap = solv_calloc(cbdata.fetchmapn + 1, sizeof(Id));
      if (cbdata.aliases)
	{
	  cbdata.fetchdirmapn = ((cbdata.fetchmapn + 1) / 16) - 1;
	  map_init(&cbdata.fetchdirmap, cbdata.fetchdirmapn + 1);
	}
    }
  lookat_cnt = cbdata.lookat.count;
  while (lookat_cnt)
    {
      Id idx = cbdata.lookat.elements[1];
      int iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
      if (usefilecolors)
	iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
      /* find end of idx block */
      for (j = 4; j < lookat_cnt; j += 4)
	if (cbdata.lookat.elements[j + 1] != idx)
	  break;
      p = pkgs->elements[idx];
      handle = (*handle_cb)(pool, p, handle_cbdata);
      if (!handle)
	{
	  queue_deleten(&cbdata.lookat, 0, j);
	  lookat_cnt -= j;
	  continue;
	}
      hdrfetches++;
      /* create hash which maps (hx, dirid) to lookat elements */
      /* also create map from dhx values for fast reject */
      for (i = 0; i < j; i += 4)
	{
	  Hashval h, hh;
	  h = (cbdata.lookat.elements[i] ^ (cbdata.lookat.elements[i + 3] * 37)) & cbdata.fetchmapn;
	  hh = HASHCHAIN_START;
	  while (cbdata.fetchmap[h])
	    h = HASHCHAIN_NEXT(h, hh, cbdata.fetchmapn);
	  cbdata.fetchmap[h] = i + 1;
	  cbdata.lookat.elements[i + 1] = (Id)h;	/* hack: misuse idx for easy hash cleanup */
	  if (cbdata.fetchdirmapn)
	    MAPSET(&cbdata.fetchdirmap, cbdata.lookat.elements[i + 2] & cbdata.fetchdirmapn);
	}
      cbdata.idx = idx;
      cbdata.lastdiridx = -1;
      cbdata.lastdiridxbad = 0;
      queue_prealloc(&cbdata.newlookat, j + 256);
      rpm_iterate_filelist(handle, iterflags, findfileconflicts_expand_cb, &cbdata);
      /* clear hash and map again */
      for (i = 0; i < j; i += 4)
	{
	  Hashval h = (Hashval)cbdata.lookat.elements[i + 1];
	  cbdata.fetchmap[h] = 0;
	  if (cbdata.fetchdirmapn)
	    MAPCLR_AT(&cbdata.fetchdirmap, cbdata.lookat.elements[i + 2] & cbdata.fetchdirmapn);
	}
      /* now delete old block and add new block to the end */
      queue_deleten(&cbdata.lookat, 0, j);
      queue_insertn(&cbdata.lookat, cbdata.lookat.count, cbdata.newlookat.count, cbdata.newlookat.elements);
      queue_empty(&cbdata.newlookat);
      lookat_cnt -= j;
    }
  queue_free(&cbdata.newlookat);
  POOL_DEBUG(SOLV_DEBUG_STATS, "header fetches: %d\n", hdrfetches);
  POOL_DEBUG(SOLV_DEBUG_STATS, "candidates now: %d\n", cbdata.lookat.count / 4);
  POOL_DEBUG(SOLV_DEBUG_STATS, "file expansion took %d ms\n", solv_timems(now));
  /* free memory */
  cbdata.fetchmap = solv_free(cbdata.fetchmap);
  cbdata.fetchmapn = 0;
  if (cbdata.fetchdirmapn)
    map_free(&cbdata.fetchdirmap);
  cbdata.fetchdirmapn = 0;
  cbdata.normap = solv_free(cbdata.normap);
  cbdata.normapn = 0;
  queue_free(&cbdata.norq);

  /* forth pass: for each (hx,dirid) we have, compare all matching files against all other matching files */
  now = solv_timems(0);
  solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 4, sizeof(Id) * 4, &lookat_hx_cmp, pool);
  for (i = 0; i < cbdata.lookat.count - 4; i += 4)
    {
      Id hx = cbdata.lookat.elements[i];
      Id dirid = cbdata.lookat.elements[i + 3];
      Id idxi = cbdata.lookat.elements[i + 1];
      Id offi = cbdata.lookat.elements[i + 2];
      if (idxi >= cutoff)
	continue;	/* no conflicts between packages with idx >= cutoff */
      for (j = i + 4; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx && cbdata.lookat.elements[j + 3] == dirid; j += 4)
	{
	  Id idxj = cbdata.lookat.elements[j + 1];
	  Id offj = cbdata.lookat.elements[j + 2];
	  char *fsi = (char *)cbdata.filesspace + offi;
	  char *fsj = (char *)cbdata.filesspace + offj;
	  if (cbdata.aliases)
	    {
	      /* compare just the basenames, the dirs match because of the dirid */
	      char *bsi = strrchr(fsi + 34, '/');
	      char *bsj = strrchr(fsj + 34, '/');
	      if (!bsi || !bsj)
		continue;
	      if (strcmp(bsi, bsj))
		continue;	/* different base names */
	    }
	  else
	    {
	      if (strcmp(fsi + 34, fsj + 34))
		continue;	/* different file names */
	    }
	  if (!strcmp(fsi, fsj))
	    continue;	/* file digests match, no conflict */
	  if (usefilecolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
	    continue;	/* colors do not conflict */
	  queue_push(conflicts, pool_str2id(pool, fsi + 34, 1));
	  queue_push(conflicts, pkgs->elements[idxi]);
	  queue_push(conflicts, pool_str2id(pool, fsi, 1));
	  queue_push(conflicts, pool_str2id(pool, fsj + 34, 1));
	  queue_push(conflicts, pkgs->elements[idxj]);
	  queue_push(conflicts, pool_str2id(pool, fsj, 1));
	}
    }
  POOL_DEBUG(SOLV_DEBUG_STATS, "filespace size: %d K\n", cbdata.filesspacen / 1024);
  POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
  cbdata.filesspace = solv_free(cbdata.filesspace);
  cbdata.filesspacen = 0;
  queue_free(&cbdata.lookat);
  if (conflicts->count > 6)
    solv_sort(conflicts->elements, conflicts->count / 6, 6 * sizeof(Id), conflicts_cmp, pool);
  POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 6);
  POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));

  return conflicts->count / 6;
}