src/dirpool.c - master - niceSOFT/libsolv

src/dirpool.c
219 строк6 KB
Michael Schroeder
Move dirs reallocation from dirpool_make_dirtraverse to dirpool_add_dir
18 май 2026, 13:48
18 май 2026, 13:48d8a3fcb
/*
 * Copyright (c) 2008, Novell Inc.
 *
 * This program is licensed under the BSD license, read LICENSE.BSD
 * for further information
 */

#include <stdio.h>
#include <string.h>

#include "pool.h"
#include "util.h"
#include "dirpool.h"

#define DIR_BLOCK 127

/* directories are stored as components,
 * components are simple ids from the string pool
 *   /usr/bin   ->  "", "usr", "bin"
 *   /usr/lib   ->  "", "usr", "lib"
 *   foo/bar    ->  "foo", "bar"
 *   /usr/games ->  "", "usr", "games"
 *
 * all directories are stores in the "dirs" array
 *   dirs[id] > 0 : component string pool id
 *   dirs[id] <= 0 : -(parent directory id)
 *
 * Directories with the same parent are stored as
 * multiple blocks. We need multiple blocks because
 * we cannot insert entries into old blocks, as that
 * would shift the ids of already used directories.
 * Each block starts with (-parent_dirid) and contains
 * component ids of the directory entries.
 * (The (-parent_dirid) entry is not a valid directory
 * id, it's just used internally)
 *
 * There is also the aux "dirtraverse" array, which
 * is created on demand to speed things up a bit.
 * if dirs[id] > 0, dirtravers[id] points to the first
 * entry in the last block with parent id.
 * if dirs[id] <= 0, dirtravers[id] points to the entry
 * in the previous block with the same parent.
 * (Thus it acts as a linked list that starts at the
 * parent dirid and chains all the blocks with that
 * parent.)
 *
 *  id    dirs[id]  dirtraverse[id]
 *   0     0           8       [no parent, block#0]
 *   1    ""           3
 *   2    -1                   [parent 1, /, block #0]
 *   3    "usr"       12
 *   4    -3                   [parent 3, /usr, block #0]
 *   5    "bin"
 *   6    "lib"
 *   7     0           1       [no parent, block#1]
 *   8    "foo"       10
 *   9    -8                   [parent 8, foo, block #0]
 *  10    "bar"
 *  11    -3           5       [parent 3, /usr, block #1]
 *  12    "games"
 *
 * to find all children of dirid 3 ("/usr"), follow the
 * dirtraverse link to 12 -> "games". Then follow the
 * dirtraverse link of this block to 5 -> "bin", "lib"
 */

void
dirpool_init(Dirpool *dp)
{
  memset(dp, 0, sizeof(*dp));
}

void
dirpool_free(Dirpool *dp)
{
  solv_free(dp->dirs);
  solv_free(dp->dirtraverse);
  solv_free(dp->dirhashtbl);
}

void
dirpool_make_dirtraverse(Dirpool *dp)
{
  Id parent, i, *dirtraverse;
  dp->dirtraverse = solv_free(dp->dirtraverse);
  if (!dp->ndirs)
    return;
  dirtraverse = solv_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK);
  for (i = 0; i < dp->ndirs; i++)
    {
      if (dp->dirs[i] > 0)
	continue;
      parent = -dp->dirs[i];
      dirtraverse[i] = dirtraverse[parent];
      dirtraverse[parent] = i + 1;
    }
  dp->dirtraverse = dirtraverse;
}

static inline Hashval
dirpool_hash_parent_comp(Id parent, Id comp)
{
  return parent + 7 * comp;
}

/* Build or rebuild the (parent, comp) -> dirid hash table.
 * This replaces the old O(B*C) dirtraverse linked-list scan
 * with O(1) amortized lookup in dirpool_add_dir. */
static void
dirpool_resize_hash(Dirpool *dp, int numnew)
{
  Hashval hm, h, hh;
  Hashtable ht;
  Id i, parent = 0;

  hm = mkmask(dp->ndirs + numnew);
  if (dp->dirhashtbl && hm <= dp->dirhashmask)
    return;
  dp->dirhashmask = hm;
  solv_free(dp->dirhashtbl);
  ht = dp->dirhashtbl = allochashtable(hm, 1);
  for (i = 2; i < dp->ndirs; i++)
    {
      if (dp->dirs[i] <= 0)
	{
	  parent = -dp->dirs[i];
	  continue;
	}
      h = dirpool_hash_parent_comp(parent, dp->dirs[i]) & hm;
      hh = HASHCHAIN_START;
      while (ht[h])
	h = HASHCHAIN_NEXT(h, hh, hm);
      ht[h] = i;
    }
}

/* Create a new block for a parent */
static void
dirpool_add_block(Dirpool *dp, Id parent)
{
  /* make room for parent entry */
  dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  /* new parent block, update dirtraverse if present */
  dp->dirs[dp->ndirs] = -parent;
  if (dp->dirtraverse)
    {
      dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
      dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
      dp->dirtraverse[parent] = dp->ndirs + 1;	/* point to future entry */
    }
  dp->ndirs++;
}

Id
dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
{
  Id did;
  Hashval h, hh, hm;
  Hashtable ht;

  if (!dp->ndirs)
    {
      if (!create)
	return 0;
      dp->ndirs = 2;
      dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
      dp->dirs[0] = 0;
      dp->dirs[1] = 1;	/* "" */
    }
  if (parent < 0 || comp <= 0)
    return 0;
  if (parent == 0 && comp == 1)
    return 1;

  /* grow hash table if load factor exceeds 50% */
  if ((Hashval)dp->ndirs * 2 >= dp->dirhashmask)
    {
      /* hack: repo_add_solv will not use DIR_BLOCK, so realloc here */
      if (!dp->dirhashmask)
        dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
      dirpool_resize_hash(dp, DIR_BLOCK);
    }

  ht = dp->dirhashtbl;
  hm = dp->dirhashmask;

  /* probe for existing (parent, comp) entry */
  h = dirpool_hash_parent_comp(parent, comp) & hm;
  hh = HASHCHAIN_START;
  while ((did = ht[h]) != 0)
    {
      if (dp->dirs[did] == comp && dirpool_parent(dp, did) == parent)
	return did;
      h = HASHCHAIN_NEXT(h, hh, hm);
    }

  if (!create)
    return 0;

  /* start a new block if the parent is different */
  if (dirpool_parent(dp, dp->ndirs - 1) != parent)
    dirpool_add_block(dp, parent);
    
  /* add new entry */
  dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
  dp->dirs[dp->ndirs] = comp;
  if (dp->dirtraverse)
    {
      dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
      dp->dirtraverse[dp->ndirs] = 0;	/* no children */
    }
  did = dp->ndirs++;

  /* insert new entry into hash table (h still points at
   * the empty slot from the failed probe above) */
  ht[h] = did;

  return did;
}