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
|
/*
* 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
void
dirpool_create(Dirpool *dp)
{
memset(dp, 0, sizeof(*dp));
}
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_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)
{
dp->ndirs = 2;
dp->dirs = sat_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);
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)
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 = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
dp->dirtraverse = sat_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[dp->ndirs] = comp;
dp->dirtraverse[dp->ndirs] = 0;
return dp->ndirs++;
}
|
