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