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 *
gdCacheCreate(int size,gdCacheTestFn_t gdCacheTest,gdCacheFetchFn_t gdCacheFetch,gdCacheReleaseFn_t gdCacheRelease)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
gdCacheDelete(gdCache_head_t * head)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 *
gdCacheGet(gdCache_head_t * head,void * keydata)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
cacheTest(void * map,void * key)159 cacheTest (void *map, void *key)
160 {
161   return (((key_value_t *) map)->key == *(int *) key);
162 }
163 
164 static void *
cacheFetch(char ** error,void * key)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
cacheRelease(void * map)178 cacheRelease (void *map)
179 {
180   gdFree ((char *) map);
181 }
182 
183 int
main(char * argv[],int argc)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 */
211