summaryrefslogtreecommitdiff
path: root/dirCache.c
diff options
context:
space:
mode:
Diffstat (limited to 'dirCache.c')
-rw-r--r--dirCache.c367
1 files changed, 367 insertions, 0 deletions
diff --git a/dirCache.c b/dirCache.c
new file mode 100644
index 0000000..e1dad23
--- /dev/null
+++ b/dirCache.c
@@ -0,0 +1,367 @@
+/* Copyright 1998,2001-2003,2007-2009 Alain Knaff.
+ * This file is part of mtools.
+ *
+ * Mtools is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Mtools is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Mtools. If not, see <http://www.gnu.org/licenses/>.
+ */
+#include "sysincludes.h"
+#include "vfat.h"
+#include "dirCache.h"
+#include "dirCacheP.h"
+#include <assert.h>
+
+
+#define BITS_PER_INT (sizeof(unsigned int) * 8)
+
+
+static __inline__ unsigned int rol(unsigned int arg, int shift)
+{
+ arg &= 0xffffffff; /* for 64 bit machines */
+ return (arg << shift) | (arg >> (32 - shift));
+}
+
+
+static int calcHash(wchar_t *name)
+{
+ unsigned long hash;
+ int i;
+ wchar_t c;
+
+ hash = 0;
+ i = 0;
+ while(*name) {
+ /* rotate it */
+ hash = rol(hash,5); /* a shift of 5 makes sure we spread quickly
+ * over the whole width, moreover, 5 is
+ * prime with 32, which makes sure that
+ * successive letters cannot cover each
+ * other easily */
+ c = towupper(*name);
+ hash ^= (c * (c+2)) ^ (i * (i+2));
+ hash &= 0xffffffff;
+ i++, name++;
+ }
+ hash = hash * (hash + 2);
+ /* the following two xors make sure all info is spread evenly over all
+ * bytes. Important if we only keep the low order bits later on */
+ hash ^= (hash & 0xfff) << 12;
+ hash ^= (hash & 0xff000) << 24;
+ return hash;
+}
+
+static int addBit(unsigned int *bitmap, int hash, int checkOnly)
+{
+ int bit, entry;
+
+ bit = 1 << (hash % BITS_PER_INT);
+ entry = (hash / BITS_PER_INT) % DC_BITMAP_SIZE;
+
+ if(checkOnly)
+ return bitmap[entry] & bit;
+ else {
+ bitmap[entry] |= bit;
+ return 1;
+ }
+}
+
+static int _addHash(dirCache_t *cache, unsigned int hash, int checkOnly)
+{
+ return
+ addBit(cache->bm0, hash, checkOnly) &&
+ addBit(cache->bm1, rol(hash,12), checkOnly) &&
+ addBit(cache->bm2, rol(hash,24), checkOnly);
+}
+
+
+static void addNameToHash(dirCache_t *cache, wchar_t *name)
+{
+ _addHash(cache, calcHash(name), 0);
+}
+
+static void hashDce(dirCache_t *cache, dirCacheEntry_t *dce)
+{
+ if(dce->beginSlot != cache->nrHashed)
+ return;
+ cache->nrHashed = dce->endSlot;
+ if(dce->longName)
+ addNameToHash(cache, dce->longName);
+ addNameToHash(cache, dce->shortName);
+}
+
+int isHashed(dirCache_t *cache, wchar_t *name)
+{
+ int ret;
+
+ ret = _addHash(cache, calcHash(name), 1);
+ return ret;
+}
+
+int growDirCache(dirCache_t *cache, int slot)
+{
+ if(slot < 0) {
+ fprintf(stderr, "Bad slot %d\n", slot);
+ exit(1);
+ }
+
+ if( cache->nr_entries <= slot) {
+ int i;
+
+ cache->entries = realloc(cache->entries,
+ (slot+1) * 2 *
+ sizeof(dirCacheEntry_t *));
+ if(!cache->entries)
+ return -1;
+ for(i= cache->nr_entries; i < (slot+1) * 2; i++) {
+ cache->entries[i] = 0;
+ }
+ cache->nr_entries = (slot+1) * 2;
+ }
+ return 0;
+}
+
+dirCache_t *allocDirCache(Stream_t *Stream, int slot)
+{
+ dirCache_t **dcp;
+
+ if(slot < 0) {
+ fprintf(stderr, "Bad slot %d\n", slot);
+ exit(1);
+ }
+
+ dcp = getDirCacheP(Stream);
+ if(!*dcp) {
+ *dcp = New(dirCache_t);
+ if(!*dcp)
+ return 0;
+ (*dcp)->entries = NewArray((slot+1)*2+5, dirCacheEntry_t *);
+ if(!(*dcp)->entries) {
+ free(*dcp);
+ return 0;
+ }
+ (*dcp)->nr_entries = (slot+1) * 2;
+ memset( (*dcp)->bm0, 0, DC_BITMAP_SIZE);
+ memset( (*dcp)->bm1, 0, DC_BITMAP_SIZE);
+ memset( (*dcp)->bm2, 0, DC_BITMAP_SIZE);
+ (*dcp)->nrHashed = 0;
+ } else
+ if(growDirCache(*dcp, slot) < 0)
+ return 0;
+ return *dcp;
+}
+
+/* Free a range of entries. The range being cleared is always aligned
+ * on the begin of an entry. Entries which are cleared entirely are
+ * free'd. Entries which are cleared half-way (can only happen at end)
+ * are "shortened" by moving its beginSlot
+ * If this was a range representing space after end-mark, return beginning
+ * of range if it had been shortened in its lifetime (which means that end
+ * mark must have moved => may need to be rewritten)
+ */
+static int freeDirCacheRange(dirCache_t *cache,
+ unsigned int beginSlot,
+ unsigned int endSlot)
+{
+ dirCacheEntry_t *entry;
+ unsigned int clearBegin;
+ unsigned int clearEnd;
+ unsigned int i;
+
+ if(endSlot < beginSlot) {
+ fprintf(stderr, "Bad slots %d %d in free range\n",
+ beginSlot, endSlot);
+ exit(1);
+ }
+
+ while(beginSlot < endSlot) {
+ entry = cache->entries[beginSlot];
+ if(!entry) {
+ beginSlot++;
+ continue;
+ }
+
+ /* Due to the way this is called, we _always_ de-allocate
+ * starting from beginning... */
+ assert(entry->beginSlot == beginSlot);
+
+ clearEnd = entry->endSlot;
+ if(clearEnd > endSlot)
+ clearEnd = endSlot;
+ clearBegin = beginSlot;
+
+ for(i = clearBegin; i <clearEnd; i++)
+ cache->entries[i] = 0;
+
+ entry->beginSlot = clearEnd;
+
+ if(entry->beginSlot == entry->endSlot) {
+ int needWriteEnd = 0;
+ if(entry->endMarkPos != -1 &&
+ entry->endMarkPos < beginSlot)
+ needWriteEnd = 1;
+
+ if(entry->longName)
+ free(entry->longName);
+ if(entry->shortName)
+ free(entry->shortName);
+ free(entry);
+ if(needWriteEnd) {
+ return beginSlot;
+ }
+ }
+
+ beginSlot = clearEnd;
+ }
+ return -1;
+}
+
+static dirCacheEntry_t *allocDirCacheEntry(dirCache_t *cache, int beginSlot,
+ int endSlot,
+ dirCacheEntryType_t type)
+{
+ dirCacheEntry_t *entry;
+ int i;
+
+ if(growDirCache(cache, endSlot) < 0)
+ return 0;
+
+ entry = New(dirCacheEntry_t);
+ if(!entry)
+ return 0;
+ entry->type = type;
+ entry->longName = 0;
+ entry->shortName = 0;
+ entry->beginSlot = beginSlot;
+ entry->endSlot = endSlot;
+ entry->endMarkPos = -1;
+
+ freeDirCacheRange(cache, beginSlot, endSlot);
+ for(i=beginSlot; i<endSlot; i++) {
+ cache->entries[i] = entry;
+ }
+ return entry;
+}
+
+dirCacheEntry_t *addUsedEntry(dirCache_t *cache, int beginSlot, int endSlot,
+ wchar_t *longName, wchar_t *shortName,
+ struct directory *dir)
+{
+ dirCacheEntry_t *entry;
+
+ if(endSlot < beginSlot) {
+ fprintf(stderr,
+ "Bad slots %d %d in add used entry\n",
+ beginSlot, endSlot);
+ exit(1);
+ }
+
+
+ entry = allocDirCacheEntry(cache, beginSlot, endSlot, DCET_USED);
+ if(!entry)
+ return 0;
+
+ entry->beginSlot = beginSlot;
+ entry->endSlot = endSlot;
+ if(longName)
+ entry->longName = wcsdup(longName);
+ entry->shortName = wcsdup(shortName);
+ entry->dir = *dir;
+ hashDce(cache, entry);
+ return entry;
+}
+
+/* Try to merge free slot at position "slot" with slot at previous position
+ * After successful merge, both will point to a same DCE (the one which used
+ * to be previous)
+ * Only does something if both of these slots are actually free
+ */
+static void mergeFreeSlots(dirCache_t *cache, int slot)
+{
+ dirCacheEntry_t *previous, *next;
+ unsigned int i;
+
+ if(slot == 0)
+ return;
+ previous = cache->entries[slot-1];
+ next = cache->entries[slot];
+ if(next && next->type == DCET_FREE &&
+ previous && previous->type == DCET_FREE) {
+ for(i=next->beginSlot; i < next->endSlot; i++)
+ cache->entries[i] = previous;
+ previous->endSlot = next->endSlot;
+ previous->endMarkPos = next->endMarkPos;
+ free(next);
+ }
+}
+
+/* Create a free range extending from beginSlot to endSlot, and try to merge
+ * it with any neighboring free ranges */
+dirCacheEntry_t *addFreeEndEntry(dirCache_t *cache,
+ unsigned int beginSlot,
+ unsigned int endSlot,
+ int isAtEnd)
+{
+ dirCacheEntry_t *entry;
+
+ if(beginSlot < cache->nrHashed)
+ cache->nrHashed = beginSlot;
+
+ if(endSlot < beginSlot) {
+ fprintf(stderr, "Bad slots %d %d in add free entry\n",
+ beginSlot, endSlot);
+ exit(1);
+ }
+
+ if(endSlot == beginSlot)
+ return 0;
+ entry = allocDirCacheEntry(cache, beginSlot, endSlot, DCET_FREE);
+ if(isAtEnd)
+ entry->endMarkPos = beginSlot;
+ mergeFreeSlots(cache, beginSlot);
+ mergeFreeSlots(cache, endSlot);
+ return cache->entries[beginSlot];
+}
+
+dirCacheEntry_t *addFreeEntry(dirCache_t *cache,
+ unsigned int beginSlot,
+ unsigned int endSlot)
+{
+ return addFreeEndEntry(cache, beginSlot, endSlot, 0);
+}
+
+dirCacheEntry_t *addEndEntry(dirCache_t *cache, int pos)
+{
+ return allocDirCacheEntry(cache, pos, pos+1, DCET_END);
+}
+
+dirCacheEntry_t *lookupInDircache(dirCache_t *cache, int pos)
+{
+ if(growDirCache(cache, pos+1) < 0)
+ return 0;
+ return cache->entries[pos];
+}
+
+void freeDirCache(Stream_t *Stream)
+{
+ dirCache_t *cache, **dcp;
+
+ dcp = getDirCacheP(Stream);
+ cache = *dcp;
+ if(cache) {
+ int n;
+ n=freeDirCacheRange(cache, 0, cache->nr_entries);
+ if(n >= 0)
+ low_level_dir_write_end(Stream, n);
+ free(cache);
+ *dcp = 0;
+ }
+}
View Lorry Controller Status