#include "cachestr.h"
#include "misc.h"
#define INITBUCKETS 64
#define INITHASHSIZE 6
#define MAXHASHSIZE 11
#define ENTRYOFFSET 22
#define CACHE_ENTRY_MASK 0x3FFFFF
#define CACHE_ENTRY_BITS(id) ((id) & 0x1fc00000)
#define CACHE_ID(id) ((int)(CACHE_ENTRY_BITS(id) >> ENTRYOFFSET))
#define NullCacheEntry ((CacheEntryPtr) 0)
#define MAX_NUM_CACHES 32
static CachePtr caches[MAX_NUM_CACHES];
static int num_caches = 1;
Cache
CacheInit(unsigned long maxsize)
{
Cache id = (Cache) num_caches;
CachePtr cache;
cache = (CachePtr) fsalloc(sizeof(CacheRec));
if (!cache)
return (Cache) 0;
cache->entries = (CacheEntryPtr *)
fsalloc(INITBUCKETS * sizeof(CacheEntryPtr));
bzero((char *) cache->entries, (INITBUCKETS * sizeof(CacheEntryPtr)));
if (!cache->entries) {
fsfree(cache);
return (Cache) 0;
}
caches[id] = cache;
cache->elements = 0;
cache->buckets = INITBUCKETS;
cache->hashsize = INITHASHSIZE;
cache->maxsize = maxsize;
cache->cursize = 0;
cache->nextid = id << ENTRYOFFSET;
cache->id = id;
num_caches++;
return id;
}
static int
hash(CacheID cid)
{
CachePtr cache = caches[CACHE_ID(cid)];
switch (cache->hashsize) {
#ifdef DEBUG
case 2:
return ((int) (0x03 & (cid ^ (cid >> 2) ^ (cid >> 8))));
case 3:
return ((int) (0x07 & (cid ^ (cid >> 3) ^ (cid >> 9))));
case 4:
return ((int) (0x0F & (cid ^ (cid >> 4) ^ (cid >> 10))));
case 5:
return ((int) (0x01F & (cid ^ (cid >> 5) ^ (cid >> 11))));
#endif
case 6:
return ((int) (0x03F & (cid ^ (cid >> 6) ^ (cid >> 12))));
case 7:
return ((int) (0x07F & (cid ^ (cid >> 7) ^ (cid >> 13))));
case 8:
return ((int) (0x0FF & (cid ^ (cid >> 8) ^ (cid >> 16))));
case 9:
return ((int) (0x1FF & (cid ^ (cid >> 9))));
case 10:
return ((int) (0x3FF & (cid ^ (cid >> 10))));
case 11:
return ((int) (0x7FF & (cid ^ (cid >> 11))));
}
return -1;
}
static void
rebuild_cache(CachePtr cache)
{
int j;
CacheEntryPtr cp,
next,
**tails,
*entries,
**tptr,
*cptr;
assert(cache);
j = 2 * cache->buckets;
tails = (CacheEntryPtr **) ALLOCATE_LOCAL(j * sizeof(CacheEntryPtr *));
if (!tails)
return;
entries = (CacheEntryPtr *) fsalloc(j * sizeof(CacheEntryPtr));
if (entries) {
DEALLOCATE_LOCAL(tails);
return;
}
for (cptr = entries, tptr = tails; --j >= 0; cptr++, tptr++) {
*cptr = NullCacheEntry;
*tptr = cptr;
}
cache->hashsize++;
for (j = cache->buckets, cptr = cache->entries; --j >= 0; cptr++) {
for (cp = *cptr; cp; cp = next) {
next = cp->next;
cp->next = NullCacheEntry;
tptr = &tails[hash(cp->id)];
**tptr = cp;
*tptr = &cp->next;
}
}
DEALLOCATE_LOCAL(tails);
cache->buckets *= 2;
fsfree(cache->entries);
cache->entries = entries;
}
void
CacheReset(void)
{
CacheEntryPtr cp;
CachePtr cache;
int i,
j;
for (j = 0; j < num_caches; j++) {
cache = caches[j];
if (!cache)
continue;
for (i = 0; i < cache->buckets; i++) {
for (cp = cache->entries[i]; cp; cp = cp->next) {
cache->elements--;
cache->cursize -= cp->size;
(*cp->free_func) (cp->id, cp->data, CacheWasReset);
fsfree(cp);
}
cache->entries[i] = (CacheEntryPtr) 0;
}
assert(cache->cursize == 0);
}
}
static void
flush_cache(CachePtr cache, unsigned long needed)
{
CacheEntryPtr cp,
oldest,
*oldprev;
int oldbucket = -1,
i;
while ((cache->cursize + needed) > cache->maxsize) {
oldest = (CacheEntryPtr) 0;
for (i = 0; i < cache->buckets; i++) {
cp = cache->entries[i];
if (!cp)
continue;
if (!oldest) {
oldbucket = i;
oldest = cp;
}
while (cp) {
if (cp->timestamp < oldest->timestamp) {
oldest = cp;
oldbucket = i;
}
cp = cp->next;
}
}
oldprev = &cache->entries[oldbucket];
cp = *oldprev;
for (; (cp = *oldprev) != 0; oldprev = &cp->next) {
if (cp == oldest) {
*oldprev = oldest->next;
break;
}
}
cache->elements--;
cache->cursize -= oldest->size;
(*oldest->free_func) (oldest->id, oldest->data, CacheEntryOld);
fsfree(oldest);
}
}
void
CacheResize(Cache cid, unsigned newsize)
{
CachePtr cache = caches[cid];
if (!cache)
return;
if (newsize < cache->maxsize) {
flush_cache(cache, cache->maxsize - newsize);
}
cache->maxsize = newsize;
}
CacheID
CacheStoreMemory(
Cache cid,
pointer data,
unsigned long size,
CacheFree free_func)
{
CacheID id;
CacheEntryPtr cp,
*head;
CachePtr cache = caches[cid];
if (size > cache->maxsize)
return (CacheID) 0;
if ((cache->elements >= 4 * cache->buckets) &&
(cache->hashsize < MAXHASHSIZE)) {
rebuild_cache(cache);
}
id = cache->nextid++;
if ((cache->cursize + size) > cache->maxsize) {
flush_cache(cache, size);
}
head = &cache->entries[hash(id)];
cp = (CacheEntryPtr) fsalloc(sizeof(CacheEntryRec));
if (!cp) {
return (CacheID) 0;
}
cp->next = *head;
cp->id = id;
cp->timestamp = GetTimeInMillis();
cp->free_func = free_func;
cp->size = size;
cp->data = data;
cache->cursize += size;
cache->elements++;
*head = cp;
return id;
}
pointer
CacheFetchMemory(
CacheID cid,
Bool update)
{
CachePtr cache = caches[CACHE_ID(cid)];
CacheEntryPtr cp,
*head;
head = &cache->entries[hash(cid)];
for (cp = *head; cp; cp = cp->next) {
if (cp->id == cid) {
if (update) {
cp->timestamp = GetTimeInMillis();
if (cp != *head) {
cp->next = *head;
*head = cp;
}
}
return cp->data;
}
}
return (pointer) 0;
}
void
CacheFreeMemory(
CacheID cid,
Bool notify)
{
CachePtr cache = caches[CACHE_ID(cid)];
CacheEntryPtr cp,
*prev,
*head;
int *elptr;
int elements;
Bool found = FALSE;
head = &cache->entries[hash(cid)];
elptr = &cache->elements;
prev = head;
while ((cp = *prev) != NullCacheEntry) {
if (cp->id == cid) {
*prev = cp->next;
elements = --*elptr;
if (notify) {
(*(cp->free_func)) (cid, cp->data, CacheEntryFreed);
}
cache->cursize -= cp->size;
fsfree(cp);
if (*elptr != elements)
prev = head;
found = TRUE;
} else {
prev = &cp->next;
}
}
if (!found)
FatalError("freeing cache entry %d which isn't there\n", cid);
}
void
CacheSimpleFree(
CacheID cid,
pointer data,
int reason)
{
fsfree(data);
}