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