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;
 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 (comp <= 0)
 114     return 0;
 115   if (parent == 0 && comp == 1)
 116     return 1;
 117   if (!dp->dirtraverse)
 118     dirpool_make_dirtraverse(dp);
 119   /* check all entries with this parent if we
 120    * already have this component */
 121   ds = dp->dirtraverse[parent];
 122   while (ds)
 123     {
 124       /* ds: first component in this block
 125        * ds-1: parent link */
 126       for (d = ds--; d < dp->ndirs; d++)
 127         {
 128           if (dp->dirs[d] == comp)
 129             return d;
 130           if (dp->dirs[d] <= 0) /* reached end of this block */
 131             break;
 132         }
 133       if (ds)
 134         ds = dp->dirtraverse[ds];
 135     }
 136   if (!create)
 137     return 0;
 138   /* a new one, find last parent */
 139   for (did = dp->ndirs - 1; did > 0; did--)
 140     if (dp->dirs[did] <= 0)
 141       break;
 142   if (dp->dirs[did] != -parent)
 143     {
 144       /* make room for parent entry */
 145       dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 146       dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 147       /* new parent block, link in */
 148       dp->dirs[dp->ndirs] = -parent;
 149       dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
 150       dp->dirtraverse[parent] = ++dp->ndirs;
 151     }
 152   /* make room for new entry */
 153   dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 154   dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
 155   dp->dirs[dp->ndirs] = comp;
 156   dp->dirtraverse[dp->ndirs] = 0;
 157   return dp->ndirs++;
 158 }