Back to index

php5  5.3.10
gdcache.c
Go to the documentation of this file.
00001 #include "gd.h"
00002 #include "gdhelpers.h"
00003 
00004 #ifdef HAVE_LIBFREETYPE
00005 #define NEED_CACHE 1
00006 #endif
00007 
00008 #ifdef NEED_CACHE
00009 
00010 /*
00011  * gdcache.c
00012  *
00013  * Caches of pointers to user structs in which the least-recently-used
00014  * element is replaced in the event of a cache miss after the cache has
00015  * reached a given size.
00016  *
00017  * John Ellson  (ellson@graphviz.org)  Oct 31, 1997
00018  *
00019  * Test this with:
00020  *               gcc -o gdcache -g -Wall -DTEST gdcache.c
00021  *
00022  * The cache is implemented by a singly-linked list of elements
00023  * each containing a pointer to a user struct that is being managed by
00024  * the cache.
00025  *
00026  * The head structure has a pointer to the most-recently-used
00027  * element, and elements are moved to this position in the list each
00028  * time they are used.  The head also contains pointers to three
00029  * user defined functions:
00030  *              - a function to test if a cached userdata matches some keydata
00031  *              - a function to provide a new userdata struct to the cache
00032  *          if there has been a cache miss.
00033  *              - a function to release a userdata struct when it is
00034  *          no longer being managed by the cache
00035  *
00036  * In the event of a cache miss the cache is allowed to grow up to
00037  * a specified maximum size.  After the maximum size is reached then
00038  * the least-recently-used element is discarded to make room for the
00039  * new.  The most-recently-returned value is always left at the
00040  * beginning of the list after retrieval.
00041  *
00042  * In the current implementation the cache is traversed by a linear
00043  * search from most-recent to least-recent.  This linear search
00044  * probably limits the usefulness of this implementation to cache
00045  * sizes of a few tens of elements.
00046  */
00047 
00048 #include "gdcache.h"
00049 
00050 /*********************************************************/
00051 /* implementation                                        */
00052 /*********************************************************/
00053 
00054 
00055 /* create a new cache */
00056 gdCache_head_t *
00057 gdCacheCreate (
00058               int size,
00059               gdCacheTestFn_t gdCacheTest,
00060               gdCacheFetchFn_t gdCacheFetch,
00061               gdCacheReleaseFn_t gdCacheRelease)
00062 {
00063   gdCache_head_t *head;
00064 
00065   head = (gdCache_head_t *) gdPMalloc(sizeof (gdCache_head_t));
00066   head->mru = NULL;
00067   head->size = size;
00068   head->gdCacheTest = gdCacheTest;
00069   head->gdCacheFetch = gdCacheFetch;
00070   head->gdCacheRelease = gdCacheRelease;
00071   return head;
00072 }
00073 
00074 void
00075 gdCacheDelete (gdCache_head_t * head)
00076 {
00077   gdCache_element_t *elem, *prev;
00078 
00079   elem = head->mru;
00080   while (elem)
00081     {
00082       (*(head->gdCacheRelease)) (elem->userdata);
00083       prev = elem;
00084       elem = elem->next;
00085       gdPFree ((char *) prev);
00086     }
00087   gdPFree ((char *) head);
00088 }
00089 
00090 void *
00091 gdCacheGet (gdCache_head_t * head, void *keydata)
00092 {
00093   int i = 0;
00094   gdCache_element_t *elem, *prev = NULL, *prevprev = NULL;
00095   void *userdata;
00096 
00097   elem = head->mru;
00098   while (elem)
00099     {
00100       if ((*(head->gdCacheTest)) (elem->userdata, keydata))
00101        {
00102          if (i)
00103            {                /* if not already most-recently-used */
00104              /* relink to top of list */
00105              prev->next = elem->next;
00106              elem->next = head->mru;
00107              head->mru = elem;
00108            }
00109          return elem->userdata;
00110        }
00111       prevprev = prev;
00112       prev = elem;
00113       elem = elem->next;
00114       i++;
00115     }
00116   userdata = (*(head->gdCacheFetch)) (&(head->error), keydata);
00117   if (!userdata)
00118     {
00119       /* if there was an error in the fetch then don't cache */
00120       return NULL;
00121     }
00122   if (i < head->size)
00123     {                       /* cache still growing - add new elem */
00124       elem = (gdCache_element_t *) gdPMalloc(sizeof (gdCache_element_t));
00125     }
00126   else
00127     {                       /* cache full - replace least-recently-used */
00128       /* preveprev becomes new end of list */
00129       prevprev->next = NULL;
00130       elem = prev;
00131       (*(head->gdCacheRelease)) (elem->userdata);
00132     }
00133   /* relink to top of list */
00134   elem->next = head->mru;
00135   head->mru = elem;
00136   elem->userdata = userdata;
00137   return userdata;
00138 }
00139 
00140 
00141 
00142 /*********************************************************/
00143 /* test stub                                             */
00144 /*********************************************************/
00145 
00146 
00147 #ifdef TEST
00148 
00149 #include <stdio.h>
00150 
00151 typedef struct
00152 {
00153   int key;
00154   int value;
00155 }
00156 key_value_t;
00157 
00158 static int
00159 cacheTest (void *map, void *key)
00160 {
00161   return (((key_value_t *) map)->key == *(int *) key);
00162 }
00163 
00164 static void *
00165 cacheFetch (char **error, void *key)
00166 {
00167   key_value_t *map;
00168 
00169   map = (key_value_t *) gdMalloc (sizeof (key_value_t));
00170   map->key = *(int *) key;
00171   map->value = 3;
00172 
00173   *error = NULL;
00174   return (void *) map;
00175 }
00176 
00177 static void
00178 cacheRelease (void *map)
00179 {
00180   gdFree ((char *) map);
00181 }
00182 
00183 int
00184 main (char *argv[], int argc)
00185 {
00186   gdCache_head_t *cacheTable;
00187   int elem, key;
00188 
00189   cacheTable = gdCacheCreate (3, cacheTest, cacheFetch, cacheRelease);
00190 
00191   key = 20;
00192   elem = *(int *) gdCacheGet (cacheTable, &key);
00193   key = 30;
00194   elem = *(int *) gdCacheGet (cacheTable, &key);
00195   key = 40;
00196   elem = *(int *) gdCacheGet (cacheTable, &key);
00197   key = 50;
00198   elem = *(int *) gdCacheGet (cacheTable, &key);
00199   key = 30;
00200   elem = *(int *) gdCacheGet (cacheTable, &key);
00201   key = 30;
00202   elem = *(int *) gdCacheGet (cacheTable, &key);
00203 
00204   gdCacheDelete (cacheTable);
00205 
00206   return 0;
00207 }
00208 
00209 #endif /* TEST */
00210 #endif /* HAVE_NEECACHE */