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