improve appdata.xml parsing

[platform/upstream/libsolv.git] / src / dirpool.c

diff --git a/src/dirpool.c b/src/dirpool.c
index e843b2a..5f08361 100644 (file)
--- a/src/dirpool.c
+++ b/src/dirpool.c
@@ -10,30 +10,81 @@
 
 #include "pool.h"
 #include "util.h"
+#include "dirpool.h"
 
 #define DIR_BLOCK 127
 
-typedef struct _Dirpool {
-  Id *dirs;
-  int ndirs;
-  Id *dirtraverse;
-} Dirpool;
+/* 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_create(Dirpool *dp)
+dirpool_init(Dirpool *dp)
 {
   memset(dp, 0, sizeof(*dp));
 }
 
 void
+dirpool_free(Dirpool *dp)
+{
+  solv_free(dp->dirs);
+  solv_free(dp->dirtraverse);
+}
+
+void
 dirpool_make_dirtraverse(Dirpool *dp)
 {
   Id parent, i, *dirtraverse;
   if (!dp->ndirs)
     return;
-  dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
-  dirtraverse = sat_extend_resize(0, dp->ndirs, sizeof(Id), DIR_BLOCK);
-  memset(dirtraverse, 0, dp->ndirs * sizeof(Id));
+  dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
+  dirtraverse = solv_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK);
   for (parent = 0, i = 0; i < dp->ndirs; i++)
     {
       if (dp->dirs[i] > 0)
@@ -52,8 +103,10 @@ dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
 
   if (!dp->ndirs)
     {
+      if (!create)
+       return 0;
       dp->ndirs = 2;
-      dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
+      dp->dirs = solv_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
       dp->dirs[0] = 0;
       dp->dirs[1] = 1; /* "" */
     }
@@ -61,6 +114,8 @@ dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
     return 1;
   if (!dp->dirtraverse)
     dirpool_make_dirtraverse(dp);
+  /* check all entries with this parent if we
+   * already have this component */
   dirtraverse = dp->dirtraverse;
   ds = dirtraverse[parent];
   while (ds)
@@ -71,7 +126,7 @@ dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
        {
          if (dp->dirs[d] == comp)
            return d;
-         if (dp->dirs[d] <= 0)
+         if (dp->dirs[d] <= 0) /* reached end of this block */
            break;
        }
       if (ds)
@@ -86,18 +141,17 @@ dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
   if (dp->dirs[did] != -parent)
     {
       /* make room for parent entry */
-      dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
-      dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
+      dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
+      dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
       /* new parent block, link in */
       dp->dirs[dp->ndirs] = -parent;
       dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
       dp->dirtraverse[parent] = ++dp->ndirs;
     }
   /* make room for new entry */
-  dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
-  dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
+  dp->dirs = solv_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
+  dp->dirtraverse = solv_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
   dp->dirs[dp->ndirs] = comp;
   dp->dirtraverse[dp->ndirs] = 0;
   return dp->ndirs++;
 }
-