source: trunk/minix/commands/i386/mtools-3.9.7/dirCache.c@ 15

Last change on this file since 15 was 9, checked in by Mattia Monga, 14 years ago

Minix 3.1.2a
File size: 6.7 KB
Line 
1#include "sysincludes.h"
2#include "vfat.h"
3#include "dirCache.h"
4
5
6void myfree(void *a)
7{
8 free(a);
9}
10
11#define free myfree
12
13
14#define BITS_PER_INT (sizeof(unsigned int) * 8)
15
16
17static inline unsigned int rol(unsigned int arg, int shift)
18{
19 arg &= 0xffffffff; /* for 64 bit machines */
20 return (arg << shift) | (arg >> (32 - shift));
21}
22
23
24static int calcHash(char *name)
25{
26 unsigned long hash;
27 int i;
28 unsigned char c;
29
30 hash = 0;
31 i = 0;
32 while(*name) {
33 /* rotate it */
34 hash = rol(hash,5); /* a shift of 5 makes sure we spread quickly
35 * over the whole width, moreover, 5 is
36 * prime with 32, which makes sure that
37 * successive letters cannot cover each
38 * other easily */
39 c = toupper(*name);
40 hash ^= (c * (c+2)) ^ (i * (i+2));
41 hash &= 0xffffffff;
42 i++, name++;
43 }
44 hash = hash * (hash + 2);
45 /* the following two xors make sure all info is spread evenly over all
46 * bytes. Important if we only keep the low order bits later on */
47 hash ^= (hash & 0xfff) << 12;
48 hash ^= (hash & 0xff000) << 24;
49 return hash;
50}
51
52static int addBit(unsigned int *bitmap, int hash, int checkOnly)
53{
54 int bit, entry;
55
56 bit = 1 << (hash % BITS_PER_INT);
57 entry = (hash / BITS_PER_INT) % DC_BITMAP_SIZE;
58
59 if(checkOnly)
60 return bitmap[entry] & bit;
61 else {
62 bitmap[entry] |= bit;
63 return 1;
64 }
65}
66
67static int _addHash(dirCache_t *cache, unsigned int hash, int checkOnly)
68{
69 return
70 addBit(cache->bm0, hash, checkOnly) &&
71 addBit(cache->bm1, rol(hash,12), checkOnly) &&
72 addBit(cache->bm2, rol(hash,24), checkOnly);
73}
74
75
76static void addNameToHash(dirCache_t *cache, char *name)
77{
78 _addHash(cache, calcHash(name), 0);
79}
80
81static void hashDce(dirCache_t *cache, dirCacheEntry_t *dce)
82{
83 if(dce->beginSlot != cache->nrHashed)
84 return;
85 cache->nrHashed = dce->endSlot;
86 if(dce->longName)
87 addNameToHash(cache, dce->longName);
88 addNameToHash(cache, dce->shortName);
89}
90
91int isHashed(dirCache_t *cache, char *name)
92{
93 int ret;
94
95 ret = _addHash(cache, calcHash(name), 1);
96 return ret;
97}
98
99void checkXYZ(dirCache_t *cache)
100{
101 if(cache->entries[2])
102 printf(" at 2 = %d\n", cache->entries[2]->beginSlot);
103}
104
105
106int growDirCache(dirCache_t *cache, int slot)
107{
108 if(slot < 0) {
109 fprintf(stderr, "Bad slot %d\n", slot);
110 exit(1);
111 }
112
113 if( cache->nr_entries <= slot) {
114 int i;
115
116 cache->entries = realloc(cache->entries,
117 (slot+1) * 2 *
118 sizeof(dirCacheEntry_t *));
119 if(!cache->entries)
120 return -1;
121 for(i= cache->nr_entries; i < (slot+1) * 2; i++) {
122 cache->entries[i] = 0;
123 }
124 cache->nr_entries = (slot+1) * 2;
125 }
126 return 0;
127}
128
129dirCache_t *allocDirCache(Stream_t *Stream, int slot)
130{
131 dirCache_t **dcp;
132
133 if(slot < 0) {
134 fprintf(stderr, "Bad slot %d\n", slot);
135 exit(1);
136 }
137
138 dcp = getDirCacheP(Stream);
139 if(!*dcp) {
140 *dcp = New(dirCache_t);
141 if(!*dcp)
142 return 0;
143 (*dcp)->entries = NewArray((slot+1)*2+5, dirCacheEntry_t *);
144 if(!(*dcp)->entries) {
145 free(*dcp);
146 return 0;
147 }
148 (*dcp)->nr_entries = (slot+1) * 2;
149 memset( (*dcp)->bm0, 0, DC_BITMAP_SIZE);
150 memset( (*dcp)->bm1, 0, DC_BITMAP_SIZE);
151 memset( (*dcp)->bm2, 0, DC_BITMAP_SIZE);
152 (*dcp)->nrHashed = 0;
153 } else
154 if(growDirCache(*dcp, slot) < 0)
155 return 0;
156 return *dcp;
157}
158
159static void freeDirCacheRange(dirCache_t *cache, int beginSlot, int endSlot)
160{
161 dirCacheEntry_t *entry;
162 int clearBegin;
163 int clearEnd;
164 int i;
165
166 if(endSlot < beginSlot) {
167 fprintf(stderr, "Bad slots %d %d in free range\n",
168 beginSlot, endSlot);
169 exit(1);
170 }
171
172 while(beginSlot < endSlot) {
173 entry = cache->entries[beginSlot];
174 if(!entry) {
175 beginSlot++;
176 continue;
177 }
178
179 clearEnd = entry->endSlot;
180 if(clearEnd > endSlot)
181 clearEnd = endSlot;
182 clearBegin = beginSlot;
183
184 for(i = clearBegin; i <clearEnd; i++)
185 cache->entries[i] = 0;
186
187 if(entry->endSlot == endSlot)
188 entry->endSlot = beginSlot;
189 else if(entry->beginSlot == beginSlot)
190 entry->beginSlot = endSlot;
191 else {
192 fprintf(stderr,
193 "Internal error, non contiguous de-allocation\n");
194 fprintf(stderr, "%d %d\n", beginSlot, endSlot);
195 fprintf(stderr, "%d %d\n", entry->beginSlot,
196 entry->endSlot);
197 exit(1);
198 }
199
200 if(entry->beginSlot == entry->endSlot) {
201 if(entry->longName)
202 free(entry->longName);
203 if(entry->shortName)
204 free(entry->shortName);
205 free(entry);
206 }
207
208 beginSlot = clearEnd;
209 }
210}
211
212static dirCacheEntry_t *allocDirCacheEntry(dirCache_t *cache, int beginSlot,
213 int endSlot,
214 dirCacheEntryType_t type)
215{
216 dirCacheEntry_t *entry;
217 int i;
218
219 if(growDirCache(cache, endSlot) < 0)
220 return 0;
221
222 entry = New(dirCacheEntry_t);
223 if(!entry)
224 return 0;
225 entry->type = type;
226 entry->longName = 0;
227 entry->shortName = 0;
228 entry->beginSlot = beginSlot;
229 entry->endSlot = endSlot;
230
231 freeDirCacheRange(cache, beginSlot, endSlot);
232 for(i=beginSlot; i<endSlot; i++) {
233 cache->entries[i] = entry;
234 }
235 return entry;
236}
237
238dirCacheEntry_t *addUsedEntry(dirCache_t *cache, int beginSlot, int endSlot,
239 char *longName, char *shortName,
240 struct directory *dir)
241{
242 dirCacheEntry_t *entry;
243
244 if(endSlot < beginSlot) {
245 fprintf(stderr,
246 "Bad slots %d %d in add used entry\n",
247 beginSlot, endSlot);
248 exit(1);
249 }
250
251
252 entry = allocDirCacheEntry(cache, beginSlot, endSlot, DCET_USED);
253 if(!entry)
254 return 0;
255
256 entry->beginSlot = beginSlot;
257 entry->endSlot = endSlot;
258 if(longName)
259 entry->longName = strdup(longName);
260 entry->shortName = strdup(shortName);
261 entry->dir = *dir;
262 hashDce(cache, entry);
263 return entry;
264}
265
266static void mergeFreeSlots(dirCache_t *cache, int slot)
267{
268 dirCacheEntry_t *previous, *next;
269 int i;
270
271 if(slot == 0)
272 return;
273 previous = cache->entries[slot-1];
274 next = cache->entries[slot];
275 if(next && next->type == DCET_FREE &&
276 previous && previous->type == DCET_FREE) {
277 for(i=next->beginSlot; i < next->endSlot; i++)
278 cache->entries[i] = previous;
279 previous->endSlot = next->endSlot;
280 free(next);
281 }
282}
283
284dirCacheEntry_t *addFreeEntry(dirCache_t *cache, int beginSlot, int endSlot)
285{
286 dirCacheEntry_t *entry;
287
288 if(beginSlot < cache->nrHashed)
289 cache->nrHashed = beginSlot;
290
291 if(endSlot < beginSlot) {
292 fprintf(stderr, "Bad slots %d %d in add free entry\n",
293 beginSlot, endSlot);
294 exit(1);
295 }
296
297 if(endSlot == beginSlot)
298 return 0;
299 entry = allocDirCacheEntry(cache, beginSlot, endSlot, DCET_FREE);
300 mergeFreeSlots(cache, beginSlot);
301 mergeFreeSlots(cache, endSlot);
302 return cache->entries[beginSlot];
303}
304
305
306dirCacheEntry_t *addEndEntry(dirCache_t *cache, int pos)
307{
308 return allocDirCacheEntry(cache, pos, pos+1, DCET_END);
309}
310
311dirCacheEntry_t *lookupInDircache(dirCache_t *cache, int pos)
312{
313 if(growDirCache(cache, pos+1) < 0)
314 return 0;
315 return cache->entries[pos];
316}
317
318void freeDirCache(Stream_t *Stream)
319{
320 dirCache_t *cache, **dcp;
321
322 dcp = getDirCacheP(Stream);
323 cache = *dcp;
324 if(cache) {
325 freeDirCacheRange(cache, 0, cache->nr_entries);
326 free(cache);
327 *dcp = 0;
328 }
329}
Note: See TracBrowser for help on using the repository browser.