root/ext/gd/libgd/gdcache.c

DEFINITIONS

1. gdCacheCreate
2. gdCacheDelete
3. gdCacheGet
4. cacheTest
5. cacheFetch
6. cacheRelease
7. main

   1 #include "gd.h"
   2 #include "gdhelpers.h"
   3 
   4 #ifdef HAVE_LIBFREETYPE
   5 #define NEED_CACHE 1
   6 #endif
   7 
   8 #ifdef NEED_CACHE
   9 
  10 /*
  11  * gdcache.c
  12  *
  13  * Caches of pointers to user structs in which the least-recently-used
  14  * element is replaced in the event of a cache miss after the cache has
  15  * reached a given size.
  16  *
  17  * John Ellson  (ellson@graphviz.org)  Oct 31, 1997
  18  *
  19  * Test this with:
  20  *               gcc -o gdcache -g -Wall -DTEST gdcache.c
  21  *
  22  * The cache is implemented by a singly-linked list of elements
  23  * each containing a pointer to a user struct that is being managed by
  24  * the cache.
  25  *
  26  * The head structure has a pointer to the most-recently-used
  27  * element, and elements are moved to this position in the list each
  28  * time they are used.  The head also contains pointers to three
  29  * user defined functions:
  30  *              - a function to test if a cached userdata matches some keydata
  31  *              - a function to provide a new userdata struct to the cache
  32  *          if there has been a cache miss.
  33  *              - a function to release a userdata struct when it is
  34  *          no longer being managed by the cache
  35  *
  36  * In the event of a cache miss the cache is allowed to grow up to
  37  * a specified maximum size.  After the maximum size is reached then
  38  * the least-recently-used element is discarded to make room for the
  39  * new.  The most-recently-returned value is always left at the
  40  * beginning of the list after retrieval.
  41  *
  42  * In the current implementation the cache is traversed by a linear
  43  * search from most-recent to least-recent.  This linear search
  44  * probably limits the usefulness of this implementation to cache
  45  * sizes of a few tens of elements.
  46  */
  47 
  48 #include "gdcache.h"
  49 
  50 /*********************************************************/
  51 /* implementation                                        */
  52 /*********************************************************/
  53 
  54 
  55 /* create a new cache */
  56 gdCache_head_t *
  57 gdCacheCreate (
  58                 int size,
  59                 gdCacheTestFn_t gdCacheTest,
  60                 gdCacheFetchFn_t gdCacheFetch,
  61                 gdCacheReleaseFn_t gdCacheRelease)
  62 {
  63   gdCache_head_t *head;
  64 
  65   head = (gdCache_head_t *) gdPMalloc(sizeof (gdCache_head_t));
  66   head->mru = NULL;
  67   head->size = size;
  68   head->gdCacheTest = gdCacheTest;
  69   head->gdCacheFetch = gdCacheFetch;
  70   head->gdCacheRelease = gdCacheRelease;
  71   return head;
  72 }
  73 
  74 void
  75 gdCacheDelete (gdCache_head_t * head)
  76 {
  77   gdCache_element_t *elem, *prev;
  78 
  79   elem = head->mru;
  80   while (elem)
  81     {
  82       (*(head->gdCacheRelease)) (elem->userdata);
  83       prev = elem;
  84       elem = elem->next;
  85       gdPFree ((char *) prev);
  86     }
  87   gdPFree ((char *) head);
  88 }
  89 
  90 void *
  91 gdCacheGet (gdCache_head_t * head, void *keydata)
  92 {
  93   int i = 0;
  94   gdCache_element_t *elem, *prev = NULL, *prevprev = NULL;
  95   void *userdata;
  96 
  97   elem = head->mru;
  98   while (elem)
  99     {
 100       if ((*(head->gdCacheTest)) (elem->userdata, keydata))
 101         {
 102           if (i)
 103             {                   /* if not already most-recently-used */
 104               /* relink to top of list */
 105               prev->next = elem->next;
 106               elem->next = head->mru;
 107               head->mru = elem;
 108             }
 109           return elem->userdata;
 110         }
 111       prevprev = prev;
 112       prev = elem;
 113       elem = elem->next;
 114       i++;
 115     }
 116   userdata = (*(head->gdCacheFetch)) (&(head->error), keydata);
 117   if (!userdata)
 118     {
 119       /* if there was an error in the fetch then don't cache */
 120       return NULL;
 121     }
 122   if (i < head->size)
 123     {                           /* cache still growing - add new elem */
 124       elem = (gdCache_element_t *) gdPMalloc(sizeof (gdCache_element_t));
 125     }
 126   else
 127     {                           /* cache full - replace least-recently-used */
 128       /* preveprev becomes new end of list */
 129       prevprev->next = NULL;
 130       elem = prev;
 131       (*(head->gdCacheRelease)) (elem->userdata);
 132     }
 133   /* relink to top of list */
 134   elem->next = head->mru;
 135   head->mru = elem;
 136   elem->userdata = userdata;
 137   return userdata;
 138 }
 139 
 140 
 141 
 142 /*********************************************************/
 143 /* test stub                                             */
 144 /*********************************************************/
 145 
 146 
 147 #ifdef TEST
 148 
 149 #include <stdio.h>
 150 
 151 typedef struct
 152 {
 153   int key;
 154   int value;
 155 }
 156 key_value_t;
 157 
 158 static int
 159 cacheTest (void *map, void *key)
 160 {
 161   return (((key_value_t *) map)->key == *(int *) key);
 162 }
 163 
 164 static void *
 165 cacheFetch (char **error, void *key)
 166 {
 167   key_value_t *map;
 168 
 169   map = (key_value_t *) gdMalloc (sizeof (key_value_t));
 170   map->key = *(int *) key;
 171   map->value = 3;
 172 
 173   *error = NULL;
 174   return (void *) map;
 175 }
 176 
 177 static void
 178 cacheRelease (void *map)
 179 {
 180   gdFree ((char *) map);
 181 }
 182 
 183 int
 184 main (char *argv[], int argc)
 185 {
 186   gdCache_head_t *cacheTable;
 187   int elem, key;
 188 
 189   cacheTable = gdCacheCreate (3, cacheTest, cacheFetch, cacheRelease);
 190 
 191   key = 20;
 192   elem = *(int *) gdCacheGet (cacheTable, &key);
 193   key = 30;
 194   elem = *(int *) gdCacheGet (cacheTable, &key);
 195   key = 40;
 196   elem = *(int *) gdCacheGet (cacheTable, &key);
 197   key = 50;
 198   elem = *(int *) gdCacheGet (cacheTable, &key);
 199   key = 30;
 200   elem = *(int *) gdCacheGet (cacheTable, &key);
 201   key = 30;
 202   elem = *(int *) gdCacheGet (cacheTable, &key);
 203 
 204   gdCacheDelete (cacheTable);
 205 
 206   return 0;
 207 }
 208 
 209 #endif /* TEST */
 210 #endif /* HAVE_NEECACHE */