src/dirpool.c

   1 /*
   2  * Copyright (c) 2008, 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 <string.h>
  10
  11 #include "pool.h"
  12 #include "util.h"
  13 #include "dirpool.h"
  14
  15 #define DIR_BLOCK 127
  16
  17 /* directories are stored as components,
  18  * components are simple ids from the string pool
  19  *   /usr/bin   ->  "", "usr", "bin"
  20  *   /usr/lib   ->  "", "usr", "lib"
  21  *   foo/bar    ->  "foo", "bar"
  22  *   /usr/games ->  "", "usr", "games"
  23  *
  24  * all directories are stores in the "dirs" array
  25  *   dirs[id] > 0 : component string pool id
  26  *   dirs[id] <= 0 : -(parent directory id)
  27  *
  28  * Directories with the same parent are stored as
  29  * multiple blocks. We need multiple blocks because
  30  * we cannot insert entries into old blocks, as that
  31  * would shift the ids of already used directories.
  32  * Each block starts with (-parent_dirid) and contains
  33  * component ids of the directory entries.
  34  * (The (-parent_dirid) entry is not a valid directory
  35  * id, it's just used internally)
  36  *
  37  * There is also the aux "dirtraverse" array, which
  38  * is created on demand to speed things up a bit.
  39  * if dirs[id] > 0, dirtravers[id] points to the first
  40  * entry in the last block with parent id.
  41  * if dirs[id] <= 0, dirtravers[id] points to the entry
  42  * in the previous block with the same parent.
  43  * (Thus it acts as a linked list that starts at the
  44  * parent dirid and chains all the blocks with that
  45  * parent.)
  46  *
  47  *  id    dirs[id]  dirtraverse[id]
  48  *   0     0           8       [no parent, block#0]
  49  *   1    ""           3
  50  *   2    -1                   [parent 1, /, block #0]
  51  *   3    "usr"       12
  52  *   4    -3                   [parent 3, /usr, block #0]
  53  *   5    "bin"
  54  *   6    "lib"
  55  *   7     0           1       [no parent, block#1]
  56  *   8    "foo"       10
  57  *   9    -8                   [parent 8, foo, block #0]
  58  *  10    "bar"
  59  *  11    -3           5       [parent 3, /usr, block #1]
  60  *  12    "games"
  61  *
  62  * to find all children of dirid 3 ("/usr"), follow the
  63  * dirtraverse link to 12 -> "games". Then follow the
  64  * dirtraverse link of this block to 5 -> "bin", "lib"
  65  */
  66
  67 void
  68 dirpool_init(Dirpool *dp)
  69 {
  70   memset(dp, 0, sizeof(*dp));
  71 }
  72
  73 void
  74 dirpool_free(Dirpool *dp)
  75 {
  76   solv_free(dp->dirs);
  77   solv_free(dp->dirtraverse);
  78 }
  79
  80 void
  81 dirpool_make_dirtraverse(Dirpool *dp)
  82 {
  83   Id parent, i, *dirtraverse;
  84   if (!dp->ndirs)
  85     return;
  86   dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
  87   dirtraverse = solv_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK);
  88   for (parent = 0, i = 0; i < dp->ndirs; i++)
  89     {
  90       if (dp->dirs[i] > 0)
  91         continue;
  92       parent = -dp->dirs[i];
  93       dirtraverse[i] = dirtraverse[parent];
  94       dirtraverse[parent] = i + 1;
  95     }
  96   dp->dirtraverse = dirtraverse;
  97 }
  98
  99 Id
 100 dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
 101 {
 102   Id did, d, ds, *dirtraverse;
 103
 104   if (!dp->ndirs)
 105     {
 106       if (!create)
 107         return 0;
 108       dp->ndirs = 2;
 109       dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
 110       dp->dirs[0] = 0;
 111       dp->dirs[1] = 1;  /* "" */
 112     }
 113   if (parent == 0 && comp == 1)
 114     return 1;
 115   if (!dp->dirtraverse)
 116     dirpool_make_dirtraverse(dp);
 117   /* check all entries with this parent if we
 118    * already have this component */
 119   dirtraverse = dp->dirtraverse;
 120   ds = dirtraverse[parent];
 121   while (ds)
 122     {
 123       /* ds: first component in this block
 124        * ds-1: parent link */
 125       for (d = ds--; d < dp->ndirs; d++)
 126         {
 127           if (dp->dirs[d] == comp)
 128             return d;
 129           if (dp->dirs[d] <= 0) /* reached end of this block */
 130             break;
 131         }
 132       if (ds)
 133         ds = dp->dirtraverse[ds];
 134     }
 135   if (!create)
 136     return 0;
 137   /* a new one, find last parent */
 138   for (did = dp->ndirs - 1; did > 0; did--)
 139     if (dp->dirs[did] <= 0)
 140       break;
 141   if (dp->dirs[did] != -parent)
 142     {
 143       /* make room for parent entry */
 144       dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 145       dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 146       /* new parent block, link in */
 147       dp->dirs[dp->ndirs] = -parent;
 148       dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
 149       dp->dirtraverse[parent] = ++dp->ndirs;
 150     }
 151   /* make room for new entry */
 152   dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 153   dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 154   dp->dirs[dp->ndirs] = comp;
 155   dp->dirtraverse[dp->ndirs] = 0;
 156   return dp->ndirs++;
 157 }