/* Cache.c v1.3 Caching control routines */
/*
This is part of ODS2 written by Paul Nankervis,
email address: Paulnank@au1.ibm.com
ODS2 is distributed freely for all members of the
VMS community to use. However all derived works
must maintain comments in their source to acknowledge
the contibution of the original author.
*/
/*
The theory is that all cachable objects share a common cache pool.
Any object with a reference count of zero is a candidate for
destruction. All cacheable objects have a 'struct CACHE' as the
first item of the object so that cache pointers and object pointers
are 'interchangeable'. All cache objects are also part of a binary
tree so that they can be located. There are many instances of these
binary trees: for files on a volume, file windows, file chunks
(segments) etc. Also each object can have an object manager: a
routine to handle special object deletion requirements (for example
to remove all file chunks before removing a file), or to flush
objects (write modified chunks to disk).
The main routines is cache_find() which is used to search for and
place objects in a binary tree which is located by a tree pointer.
cache_touch() and cache_untouch() are used to bump and decrement
reference counts. Any object with a reference count of zero is a
candidate for destruction - but if it requires special action
before it is destroyed, such as deleting a subtree, flushing data
to disk, etc, then it should have an 'object manager' function
assigned which will be called at deletion time to take care of these
needs.
This version of the cache routines attempts to maintain binary tree
balance by dynamically changing tree shape during search functions.
All objects remain in the binary tree until destruction so that they
can be re-used at any time. Objects with a zero reference count are
special in that they are kept in a 'least recently used' linked list.
When the reference count is decemented a flag is used to indicate
whether the object is likely to be referenced again so that the object
can be put in the 'correct' end of this list.
Note: These routines are 'general' in that do not know anything
about ODS2 objects or structures....
*/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "ssdef.h"
#include "cache.h"
#define DEBUG /* Debug mode? */
#define IMBALANCE 5 /* Tree imbalance limit */
#define CACHELIM 256 /* Free object limit */
#define CACHEGOAL 128 /* Free object goal */
int cachefinds = 0;
int cachecreated = 0;
int cachepurges = 0;
int cachepeak = 0;
int cachecount = 0;
int cachefreecount = 0;
int cachedeletes = 0;
int cachedeleteing = 0; /* Cache deletion in progress... */
struct CACHE lrulist = {&lrulist,&lrulist,NULL,NULL,NULL,NULL,0,0,1,0};
/* cache_show() - to print cache statistics */
void cache_show(void)
{
printf("CACHE_SHOW Find %d Create %d Purge %d Peak %d Count %d Free %d\n",
cachefinds,cachecreated,cachepurges,cachepeak,cachecount,cachefreecount);
if (cachecreated - cachedeletes != cachecount) printf(" - Deleted %d\n",cachedeletes);
}
/* cache_refcount() - compute reference count for cache subtree... */
int cache_refcount(struct CACHE *cacheobj)
{
register int refcount = 0;
if (cacheobj != NULL) {
refcount = cacheobj->refcount;
if (cacheobj->left != NULL) refcount += cache_refcount(cacheobj->left);
if (cacheobj->right != NULL) refcount += cache_refcount(cacheobj->right);
}
return refcount;
}
/* cache_delete() - blow away item from cache - allow item to select a proxy (!)
and adjust 'the tree' containing the item. */
struct CACHE *cache_delete(struct CACHE *cacheobj)
{
while (cacheobj->objmanager != NULL) {
register struct CACHE *proxyobj;
cachedeleteing = 1;
proxyobj = (*cacheobj->objmanager) (cacheobj,0);
cachedeleteing = 0;
if (proxyobj == NULL) return NULL;
if (proxyobj == cacheobj) break;
cacheobj = proxyobj;
}
#ifdef DEBUG
if (cachedeleteing != 0) printf("CACHE deletion while delete in progress\n");
#endif
if (cacheobj->refcount != 0) {
#ifdef DEBUG
printf("CACHE attempt to delete referenced object %d:%d\n",
cacheobj->objtype,cacheobj->hashval);
#endif
return NULL;
}
cacheobj->lastlru->nextlru = cacheobj->nextlru;
cacheobj->nextlru->lastlru = cacheobj->lastlru;
if (cacheobj->left == NULL) {
if (cacheobj->right == NULL) {
*(cacheobj->parent) = NULL;
} else {
cacheobj->right->parent = cacheobj->parent;
*(cacheobj->parent) = cacheobj->right;
}
} else {
if (cacheobj->right == NULL) {
cacheobj->left->parent = cacheobj->parent;
*(cacheobj->parent) = cacheobj->left;
} else {
register struct CACHE *path = cacheobj->right;
if (path->left != NULL) {
do {
path = path->left;
} while (path->left != NULL);
*(path->parent) = path->right;
if (path->right != NULL) path->right->parent = path->parent;
path->right = cacheobj->right;
path->right->parent = &path->right;
}
path->left = cacheobj->left;
path->left->parent = &path->left;
path->parent = cacheobj->parent;
*(cacheobj->parent) = path;
path->balance = 0;
}
}
cachecount--;
cachefreecount--;
cachedeletes++;
#ifdef DEBUG
cacheobj->nextlru = NULL;
cacheobj->lastlru = NULL;
cacheobj->left = NULL;
cacheobj->right = NULL;
cacheobj->parent = NULL;
cacheobj->objmanager = NULL;
cacheobj->hashval = 0;
cacheobj->balance = 0;
cacheobj->refcount = 0;
#endif
free(cacheobj);
return cacheobj;
}
/* cache_purge() - trim size of free list */
void cache_purge(void)
{
if (cachedeleteing == 0) {
register struct CACHE *cacheobj = lrulist.lastlru;
cachepurges++;
while (cachefreecount > CACHEGOAL && cacheobj != &lrulist) {
register struct CACHE *lastobj = cacheobj->lastlru;
#ifdef DEBUG
if (cacheobj->lastlru->nextlru != cacheobj ||
cacheobj->nextlru->lastlru != cacheobj ||
*(cacheobj->parent) != cacheobj) {
printf("CACHE pointers in bad shape!\n");
}
#endif
if (cacheobj->refcount == 0) {
if (cache_delete(cacheobj) != lastobj) cacheobj = lastobj;
} else {
cacheobj = lastobj;
}
}
}
}
/* cache_flush() - flush modified entries in cache */
void cache_flush(void)
{
register struct CACHE *cacheobj = lrulist.lastlru;
while (cacheobj != &lrulist) {
if (cacheobj->objmanager != NULL) {
(*cacheobj->objmanager) (cacheobj,1);
}
cacheobj = cacheobj->lastlru;
}
}
/* cache_remove() - delete all possible objects from cache subtree */
void cache_remove(struct CACHE *cacheobj)
{
if (cacheobj != NULL) {
if (cacheobj->left != NULL) cache_remove(cacheobj->left);
if (cacheobj->right != NULL) cache_remove(cacheobj->right);
if (cacheobj->refcount == 0) {
struct CACHE *delobj;
do {
delobj = cache_delete(cacheobj);
} while (delobj != NULL && delobj != cacheobj);
}
}
}
/* cache_touch() - to increase the access count on an object... */
void cache_touch(struct CACHE *cacheobj)
{
if (cacheobj->refcount++ == 0) {
#ifdef DEBUG
if (cacheobj->nextlru == NULL || cacheobj->lastlru == NULL) {
printf("CACHE LRU pointers corrupt!\n");
}
#endif
cacheobj->nextlru->lastlru = cacheobj->lastlru;
cacheobj->lastlru->nextlru = cacheobj->nextlru;
cacheobj->nextlru = NULL;
cacheobj->lastlru = NULL;
cachefreecount--;
}
}
/* cache_untouch() - to deaccess an object... */
void cache_untouch(struct CACHE *cacheobj,int recycle)
{
if (cacheobj->refcount > 0) {
if (--cacheobj->refcount == 0) {
if (++cachefreecount >= CACHELIM) cache_purge();
#ifdef DEBUG
if (cacheobj->nextlru != NULL || cacheobj->lastlru != NULL) {
printf("CACHE LRU pointers corrupt\n");
}
#endif
if (recycle) {
cacheobj->nextlru = lrulist.nextlru;
cacheobj->lastlru = &lrulist;
cacheobj->nextlru->lastlru = cacheobj;
lrulist.nextlru = cacheobj;
} else {
cacheobj->lastlru = lrulist.lastlru;
cacheobj->nextlru = &lrulist;
cacheobj->lastlru->nextlru = cacheobj;
lrulist.lastlru = cacheobj;
}
}
#ifdef DEBUG
} else {
printf("CACHE untouch limit exceeded\n");
#endif
}
}
/* cache_find() - to find or create cache entries...
The grand plan here was to use a hash code as a quick key
and call a compare function for duplicates. So far no data
type actually works like this - they either have a unique binary
key, or all records rely on the compare function - sigh!
Never mind, the potential is there! :-)
This version will call a creation function to allocate and
initialize an object if it is not found.
*/
void *cache_find(void **root,unsigned hashval,void *keyval,unsigned *retsts,
int (*compare_func) (unsigned hashval,void *keyval,void *node),
void *(*create_func) (unsigned hashval,void *keyval,unsigned *retsts))
{
register struct CACHE *cacheobj,**parent = (struct CACHE **) root;
cachefinds++;
while ((cacheobj = *parent) != NULL) {
register int cmp = hashval - cacheobj->hashval;
#ifdef DEBUG
if (cacheobj->parent != parent) {
printf("CACHE Parent pointer is corrupt\n");
}
#endif
if (cmp == 0 && compare_func != NULL) cmp = (*compare_func) (hashval,keyval,cacheobj);
if (cmp == 0) {
cache_touch(cacheobj);
if (retsts != NULL) *retsts = SS$_NORMAL;
return cacheobj;
}
if (cmp < 0) {
#ifdef IMBALANCE
register struct CACHE *left_path = cacheobj->left;
if (left_path != NULL && cacheobj->balance-- < -IMBALANCE) {
cacheobj->left = left_path->right;
if (cacheobj->left != NULL) cacheobj->left->parent = &cacheobj->left;
left_path->right = cacheobj;
cacheobj->parent = &left_path->right;
*parent = left_path;
left_path->parent = parent;
cacheobj->balance = 0;
} else {
parent = &cacheobj->left;
}
} else {
register struct CACHE *right_path = cacheobj->right;
if (right_path != NULL && cacheobj->balance++ > IMBALANCE) {
cacheobj->right = right_path->left;
if (cacheobj->right != NULL) cacheobj->right->parent = &cacheobj->right;
right_path->left = cacheobj;
cacheobj->parent = &right_path->left;
*parent = right_path;
right_path->parent = parent;
cacheobj->balance = 0;
} else {
parent = &cacheobj->right;
}
#else
parent = &cacheobj->left;
} else {
parent = &cacheobj->right;
#endif
}
}
if (create_func == NULL) {
if (retsts != NULL) *retsts = SS$_ITEMNOTFOUND;
} else {
cacheobj = (*create_func) (hashval,keyval,retsts);
if (cacheobj != NULL) {
cacheobj->nextlru = NULL;
cacheobj->lastlru = NULL;
cacheobj->left = NULL;
cacheobj->right = NULL;
cacheobj->parent = parent;
cacheobj->hashval = hashval;
cacheobj->balance = 0;
cacheobj->refcount = 1;
*parent = cacheobj;
cachecreated++;
if (cachecount++ >= cachepeak) cachepeak = cachecount;
}
}
return cacheobj;
}
syntax highlighted by Code2HTML, v. 0.9.1