1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
/*
* 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);
}
void
dirpool_make_dirtraverse(Dirpool *dp)
{
Id parent, i, *dirtraverse;
if (!dp->ndirs)
return;
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)
continue;
parent = -dp->dirs[i];
dirtraverse[i] = dirtraverse[parent];
dirtraverse[parent] = i + 1;
}
dp->dirtraverse = dirtraverse;
}
Id
dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
{
Id did, d, ds, *dirtraverse;
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 == 1)
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)
{
/* ds: first component in this block
* ds-1: parent link */
for (d = ds--; d < dp->ndirs; d++)
{
if (dp->dirs[d] == comp)
return d;
if (dp->dirs[d] <= 0) /* reached end of this block */
break;
}
if (ds)
ds = dp->dirtraverse[ds];
}
if (!create)
return 0;
/* a new one, find last parent */
for (did = dp->ndirs - 1; did > 0; did--)
if (dp->dirs[did] <= 0)
break;
if (dp->dirs[did] != -parent)
{
/* make room for parent entry */
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 = 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++;
}
|
