Back to index

php5  5.3.10
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 #include <stdlib.h>
00044 #ifdef HAVE_MALLOC_H
00045  #include <malloc.h>
00046 #endif
00047 #ifndef NULL
00048 #define NULL (void *)0
00049 #endif
00050 
00051 /* user defined function templates */
00052 typedef int (*gdCacheTestFn_t)(void *userdata, void *keydata);
00053 typedef void *(*gdCacheFetchFn_t)(char **error, void *keydata);
00054 typedef void (*gdCacheReleaseFn_t)(void *userdata);
00055 
00056 /* element structure */
00057 typedef struct gdCache_element_s gdCache_element_t;
00058 struct gdCache_element_s {
00059        gdCache_element_t    *next;
00060        void                 *userdata;
00061 };
00062 
00063 /* head structure */
00064 typedef struct gdCache_head_s gdCache_head_t;
00065 struct gdCache_head_s {
00066        gdCache_element_t    *mru;
00067        int                                size;
00068        char                        *error;
00069        gdCacheTestFn_t             gdCacheTest;
00070        gdCacheFetchFn_t     gdCacheFetch;
00071        gdCacheReleaseFn_t   gdCacheRelease;
00072 };
00073 
00074 /* function templates */
00075 gdCache_head_t *
00076 gdCacheCreate(
00077        int                                size,
00078        gdCacheTestFn_t             gdCacheTest,
00079        gdCacheFetchFn_t     gdCacheFetch,
00080        gdCacheReleaseFn_t   gdCacheRelease );
00081 
00082 void
00083 gdCacheDelete( gdCache_head_t *head );
00084 
00085 void *
00086 gdCacheGet( gdCache_head_t *head, void *keydata );