Back to index

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