/* * NAME: cache.c * DESCRIPTION: new generic cache */ inherit "/std/string"; # define DEFAULT_SIZE 10 private string *keys; /* array of cache keys */ private mixed *values; /* array of cache values */ private mapping cache; /* key -> index pairs */ private string next; /* pointers to next cache items */ private string prev; /* pointers to previous cache items */ private int head; /* most recent inserted item */ private int tail; /* least recent inserted item */ /* * NAME: reset() * DESCRIPTION: clear the cache */ static varargs void reset(int size) { int i; if (size <= 0) size = sizeof(keys); keys = allocate(size); values = allocate(size); cache = ([ ]); next = prev = space(size); for (i = 0; i < size; ++i) { next[i] = i + 1; prev[i] = i - 1; } head = 0; tail = size - 1; } /* * NAME: create() * DESCRIPTION: initialize data */ static void create(void) { reset(DEFAULT_SIZE); } /* * NAME: hit() * DESCRIPTION: move an item to the head of the cache */ private mixed hit(int item) { if (item != head) { if (item == tail) tail = prev[item]; else { int n, p; n = next[item]; p = prev[item]; next[p] = n; prev[n] = p; } next[item] = head; prev[head] = item; head = item; } return values[item]; } static mixed cache_miss(string key); /* * NAME: miss() * DESCRIPTION: insert a new item into the cache */ private mixed miss(string key) { int item; cache[keys[item = tail]] = 0; cache[keys[item] = key] = item + 1; tail = prev[item]; next[item] = head; prev[head] = item; return values[head = item] = cache_miss(key); } /* * NAME: fetch() * DESCRIPTION: return an item from the cache */ static mixed fetch(string key) { int item; if ((item = cache[key]) != 0) return hit(item - 1); else return miss(key); } /* * NAME: dump() * DESCRIPTION: return cache contents (debugging) */ static mixed *dump(void) { int *nlist, *plist, i; nlist = allocate(strlen(next)); plist = allocate(strlen(prev)); for (i = sizeof(nlist); i--; ) nlist[i] = next[i]; for (i = sizeof(plist); i--; ) plist[i] = prev[i]; return ({ keys, values, cache, nlist, plist, head, tail }); }