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
dirpool_init(Dirpool * dp)68 dirpool_init(Dirpool *dp)
69 {
70 memset(dp, 0, sizeof(*dp));
71 }
72
73 void
dirpool_free(Dirpool * dp)74 dirpool_free(Dirpool *dp)
75 {
76 solv_free(dp->dirs);
77 solv_free(dp->dirtraverse);
78 }
79
80 void
dirpool_make_dirtraverse(Dirpool * dp)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
dirpool_add_dir(Dirpool * dp,Id parent,Id comp,int create)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 }
158