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