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
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067 void
00068 dirpool_init(Dirpool *dp)
00069 {
00070 memset(dp, 0, sizeof(*dp));
00071 }
00072
00073 void
00074 dirpool_free(Dirpool *dp)
00075 {
00076 sat_free(dp->dirs);
00077 sat_free(dp->dirtraverse);
00078 }
00079
00080 void
00081 dirpool_make_dirtraverse(Dirpool *dp)
00082 {
00083 Id parent, i, *dirtraverse;
00084 if (!dp->ndirs)
00085 return;
00086 dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
00087 dirtraverse = sat_calloc_block(dp->ndirs, sizeof(Id), DIR_BLOCK);
00088 for (parent = 0, i = 0; i < dp->ndirs; i++)
00089 {
00090 if (dp->dirs[i] > 0)
00091 continue;
00092 parent = -dp->dirs[i];
00093 dirtraverse[i] = dirtraverse[parent];
00094 dirtraverse[parent] = i + 1;
00095 }
00096 dp->dirtraverse = dirtraverse;
00097 }
00098
00099 Id
00100 dirpool_add_dir(Dirpool *dp, Id parent, Id comp, int create)
00101 {
00102 Id did, d, ds, *dirtraverse;
00103
00104 if (!dp->ndirs)
00105 {
00106 if (!create)
00107 return 0;
00108 dp->ndirs = 2;
00109 dp->dirs = sat_extend_resize(dp->dirs, dp->ndirs, sizeof(Id), DIR_BLOCK);
00110 dp->dirs[0] = 0;
00111 dp->dirs[1] = 1;
00112 }
00113 if (parent == 0 && comp == 1)
00114 return 1;
00115 if (!dp->dirtraverse)
00116 dirpool_make_dirtraverse(dp);
00117
00118
00119 dirtraverse = dp->dirtraverse;
00120 ds = dirtraverse[parent];
00121 while (ds)
00122 {
00123
00124
00125 for (d = ds--; d < dp->ndirs; d++)
00126 {
00127 if (dp->dirs[d] == comp)
00128 return d;
00129 if (dp->dirs[d] <= 0)
00130 break;
00131 }
00132 if (ds)
00133 ds = dp->dirtraverse[ds];
00134 }
00135 if (!create)
00136 return 0;
00137
00138 for (did = dp->ndirs - 1; did > 0; did--)
00139 if (dp->dirs[did] <= 0)
00140 break;
00141 if (dp->dirs[did] != -parent)
00142 {
00143
00144 dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00145 dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00146
00147 dp->dirs[dp->ndirs] = -parent;
00148 dp->dirtraverse[dp->ndirs] = dp->dirtraverse[parent];
00149 dp->dirtraverse[parent] = ++dp->ndirs;
00150 }
00151
00152 dp->dirs = sat_extend(dp->dirs, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00153 dp->dirtraverse = sat_extend(dp->dirtraverse, dp->ndirs, 1, sizeof(Id), DIR_BLOCK);
00154 dp->dirs[dp->ndirs] = comp;
00155 dp->dirtraverse[dp->ndirs] = 0;
00156 return dp->ndirs++;
00157 }