dirCache.c

   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
  27 static __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
  34 static 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
  62 static 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
  77 static 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
  86 static void addNameToHash(dirCache_t *cache, wchar_t *name)
  87 {
  88         _addHash(cache, calcHash(name), 0);
  89 }
  90
  91 static 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
 101 int isHashed(dirCache_t *cache, wchar_t *name)
 102 {
 103         int ret;
 104
 105         ret =  _addHash(cache, calcHash(name), 1);
 106         return ret;
 107 }
 108
 109 int 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
 132 dirCache_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
 162 static 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
 217 static 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
 243 dirCacheEntry_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
 271 static 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
 289 dirCacheEntry_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
 313 dirCacheEntry_t *addEndEntry(dirCache_t *cache, int pos)
 314 {
 315         return allocDirCacheEntry(cache, pos, pos+1, DCET_END);
 316 }
 317
 318 dirCacheEntry_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
 325 void 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 }