Back to index

plt-scheme  4.2.1
gdcache.h
Go to the documentation of this file.
00001 /* 
00002  * gdcache.h
00003  *
00004  * Caches of pointers to user structs in which the least-recently-used 
00005  * element is replaced in the event of a cache miss after the cache has 
00006  * reached a given size.
00007  *
00008  * John Ellson  (ellson@graphviz.org)  Oct 31, 1997
00009  *
00010  * Test this with:
00011  *             gcc -o gdcache -g -Wall -DTEST gdcache.c
00012  *
00013  * The cache is implemented by a singly-linked list of elements
00014  * each containing a pointer to a user struct that is being managed by
00015  * the cache.
00016  *
00017  * The head structure has a pointer to the most-recently-used
00018  * element, and elements are moved to this position in the list each
00019  * time they are used.  The head also contains pointers to three
00020  * user defined functions: 
00021  *            - a function to test if a cached userdata matches some keydata 
00022  *            - a function to provide a new userdata struct to the cache 
00023  *          if there has been a cache miss.
00024  *            - a function to release a userdata struct when it is
00025  *          no longer being managed by the cache
00026  *
00027  * In the event of a cache miss the cache is allowed to grow up to
00028  * a specified maximum size.  After the maximum size is reached then
00029  * the least-recently-used element is discarded to make room for the 
00030  * new.  The most-recently-returned value is always left at the 
00031  * beginning of the list after retrieval.
00032  *
00033  * In the current implementation the cache is traversed by a linear
00034  * search from most-recent to least-recent.  This linear search
00035  * probably limits the usefulness of this implementation to cache
00036  * sizes of a few tens of elements.
00037  */
00038 
00039 /*********************************************************/
00040 /* header                                                */
00041 /*********************************************************/
00042 
00043 #ifdef HAVE_CONFIG_H
00044 #include "config.h"
00045 #endif
00046 
00047 #include <stdlib.h>
00048 #ifndef NULL
00049 #define NULL (void *)0
00050 #endif
00051 
00052 /* user defined function templates */
00053 typedef int (*gdCacheTestFn_t) (void *userdata, void *keydata);
00054 typedef void *(*gdCacheFetchFn_t) (char **error, void *keydata);
00055 typedef void (*gdCacheReleaseFn_t) (void *userdata);
00056 
00057 /* element structure */
00058 typedef struct gdCache_element_s gdCache_element_t;
00059 struct gdCache_element_s
00060 {
00061   gdCache_element_t *next;
00062   void *userdata;
00063 };
00064 
00065 /* head structure */
00066 typedef struct gdCache_head_s gdCache_head_t;
00067 struct gdCache_head_s
00068 {
00069   gdCache_element_t *mru;
00070   int size;
00071   char *error;
00072   gdCacheTestFn_t gdCacheTest;
00073   gdCacheFetchFn_t gdCacheFetch;
00074   gdCacheReleaseFn_t gdCacheRelease;
00075 };
00076 
00077 /* function templates */
00078 gdCache_head_t *gdCacheCreate (int size,
00079                             gdCacheTestFn_t gdCacheTest,
00080                             gdCacheFetchFn_t gdCacheFetch,
00081                             gdCacheReleaseFn_t gdCacheRelease);
00082 
00083 void gdCacheDelete (gdCache_head_t * head);
00084 
00085 void *gdCacheGet (gdCache_head_t * head, void *keydata);