Back to index

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