dirpool.c
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008 #include <stdio.h>
00009 #include <string.h>
00010
00011 #include "pool.h"
00012 #include "util.h"
00013 #include "dirpool.h"
00014
00015 #define DIR_BLOCK 127
00016
00017 void
00018 dirpool_init(Dirpool *dp)
00019 {
00020 memset(dp, 0, sizeof(*dp));
00021 }
00022
00023 void
00024 dirpool_free(Dirpool *dp)
00025 {
00026 sat_free(dp->dirs);
00027 sat_free(dp->dirtraverse);
00028 }
00029
00030 void
00031 dirpool_make_dirtraverse(Dirpool *dp)
00032 {
00033 Id parent, i, *dirtraverse;
00034 if (!dp->ndirs)
00035 return;
00036 dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
00037 dirtraverse = sat_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK);
00038 for (parent = 0, i = 0; i < dp->ndirs; i++)
00039 {
00040 if (dp->dirs[i] > 0)
00041 continue;
00042 parent = -dp->dirs[i];
00043 dirtraverse[i] = dirtraverse[parent];
00044 dirtraverse[parent] = i + 1;
00045 }
00046 dp->dirtraverse = dirtraverse;
00047 }
00048
00049 Id
00050 dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
00051 {
00052 Id did, d, ds, *dirtraverse;
00053
00054 if (!dp->ndirs)
00055 {
00056 if (!create)
00057 return 0;
00058 dp->ndirs = 2;
00059 dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
00060 dp->dirs[0] = 0;
00061 dp->dirs[1] = 1;
00062 }
00063 if (parent == 0 && comp == 1)
00064 return 1;
00065 if (!dp->dirtraverse)
00066 dirpool_make_dirtraverse(dp);
00067 dirtraverse = dp->dirtraverse;
00068 ds = dirtraverse[parent];
00069 while (ds)
00070 {
00071
00072
00073 for (d = ds--; d < dp->ndirs; d++)
00074 {
00075 if (dp->dirs[d] == comp)
00076 return d;
00077 if (dp->dirs[d] <= 0)
00078 break;
00079 }
00080 if (ds)
00081 ds = dp->dirtraverse[ds];
00082 }
00083 if (!create)
00084 return 0;
00085
00086 for (did = dp->ndirs - 1; did > 0; did--)
00087 if (dp->dirs[did] <= 0)
00088 break;
00089 if (dp->dirs[did] != -parent)
00090 {
00091
00092 dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00093 dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00094
00095 dp->dirs[dp->ndirs] = -parent;
00096 dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
00097 dp->dirtraverse[parent] = ++dp->ndirs;
00098 }
00099
00100 dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00101 dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00102 dp->dirs[dp->ndirs] = comp;
00103 dp->dirtraverse[dp->ndirs] = 0;
00104 return dp->ndirs++;
00105 }