2 * Copyright (c) 2008, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
16 typedef struct _Dirpool {
23 dirpool_create(Dirpool *dp)
25 memset(dp, 0, sizeof(*dp));
29 dirpool_make_dirtraverse(Dirpool *dp)
31 Id parent, i, *dirtraverse;
34 dp->dirs = sat_realloc2(dp->dirs, (dp->ndirs + DIR_BLOCK) &~ DIR_BLOCK, sizeof(Id));
35 dirtraverse = sat_calloc((dp->ndirs + DIR_BLOCK) &~ DIR_BLOCK, sizeof(Id));
36 for (parent = 0, i = 0; i < dp->ndirs; i++)
40 parent = -dp->dirs[i];
41 dirtraverse[i] = dirtraverse[parent];
42 dirtraverse[parent] = i + 1;
44 dp->dirtraverse = dirtraverse;
48 dirpool_add_dir(Dirpool *dp, Id parent, Id comp)
50 Id did, d, ds, *dirtraverse;
54 dp->dirs = sat_malloc2(DIR_BLOCK, sizeof(Id));
57 dp->dirs[1] = 1; /* "" */
59 if (parent == 0 && comp == 1)
62 dirpool_make_dirtraverse(dp);
63 dirtraverse = dp->dirtraverse;
64 ds = dirtraverse[parent];
67 /* ds: first component in this block
68 * ds-1: parent link */
69 for (d = ds--; d < dp->ndirs; d++)
71 if (dp->dirs[d] == comp)
77 ds = dp->dirtraverse[ds];
79 /* a new one, find last parent */
80 for (did = dp->ndirs - 1; did > 0; did--)
81 if (dp->dirs[did] <= 0)
83 if (dp->dirs[did] != -parent)
85 if ((dp->ndirs & DIR_BLOCK) == 0)
87 dp->dirs = sat_realloc2(dp->dirs, dp->ndirs + DIR_BLOCK, sizeof(Id));
88 dp->dirtraverse = sat_realloc2(dp->dirtraverse, dp->ndirs + DIR_BLOCK, sizeof(Id));
90 /* new parent block, link in */
91 dp->dirs[dp->ndirs] = -parent;
92 dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
93 dp->dirtraverse[parent] = ++dp->ndirs;
95 if ((dp->ndirs & DIR_BLOCK) == 0)
97 dp->dirs = sat_realloc2(dp->dirs, dp->ndirs + DIR_BLOCK, sizeof(Id));
98 dp->dirtraverse = sat_realloc2(dp->dirtraverse, dp->ndirs + DIR_BLOCK, sizeof(Id));
100 dp->dirs[dp->ndirs] = comp;
101 dp->dirtraverse[dp->ndirs] = 0;