1 /*
2 * $Id$
3 *
4 * Caches of pointers to user structs in which the least-recently-used
5 * element is replaced in the event of a cache miss after the cache has
6 * reached a given size.
7 *
8 * John Ellson (ellson@lucent.com) Oct 31, 1997
9 *
10 * Test this with:
11 * gcc -o gdcache -g -Wall -DTEST gdcache.c
12 *
13 * The cache is implemented by a singly-linked list of elements
14 * each containing a pointer to a user struct that is being managed by
15 * the cache.
16 *
17 * The head structure has a pointer to the most-recently-used
18 * element, and elements are moved to this position in the list each
19 * time they are used. The head also contains pointers to three
20 * user defined functions:
21 * - a function to test if a cached userdata matches some keydata
22 * - a function to provide a new userdata struct to the cache
23 * if there has been a cache miss.
24 * - a function to release a userdata struct when it is
25 * no longer being managed by the cache
26 *
27 * In the event of a cache miss the cache is allowed to grow up to
28 * a specified maximum size. After the maximum size is reached then
29 * the least-recently-used element is discarded to make room for the
30 * new. The most-recently-returned value is always left at the
31 * beginning of the list after retrieval.
32 *
33 * In the current implementation the cache is traversed by a linear
34 * search from most-recent to least-recent. This linear search
35 * probably limits the usefulness of this implementation to cache
36 * sizes of a few tens of elements.
37 */
38
39 #include "php.h"
40
41 /* This just seems unessacary */
42 #if PHP_WIN32
43 #define ENABLE_GD_TTF
44 #else
45 #include <php_config.h>
46 #endif
47 #if HAVE_LIBFREETYPE && !defined(HAVE_GD_BUNDLED)
48
49 #include "gdcache.h"
50
51 /*********************************************************/
52 /* implementation */
53 /*********************************************************/
54
55
56 /* create a new cache */
57 gdCache_head_t *
gdCacheCreate(int size,gdCacheTestFn_t gdCacheTest,gdCacheFetchFn_t gdCacheFetch,gdCacheReleaseFn_t gdCacheRelease)58 gdCacheCreate(
59 int size,
60 gdCacheTestFn_t gdCacheTest,
61 gdCacheFetchFn_t gdCacheFetch,
62 gdCacheReleaseFn_t gdCacheRelease )
63 {
64 gdCache_head_t *head;
65
66 head = (gdCache_head_t *)pemalloc(sizeof(gdCache_head_t), 1);
67 head->mru = NULL;
68 head->size = size;
69 head->gdCacheTest = gdCacheTest;
70 head->gdCacheFetch = gdCacheFetch;
71 head->gdCacheRelease = gdCacheRelease;
72 return head;
73 }
74
75 void
gdCacheDelete(gdCache_head_t * head)76 gdCacheDelete( gdCache_head_t *head )
77 {
78 gdCache_element_t *elem, *prev;
79
80 elem = head->mru;
81 while(elem) {
82 (*(head->gdCacheRelease))(elem->userdata);
83 prev = elem;
84 elem = elem->next;
85 pefree((char *)prev, 1);
86 }
87 pefree((char *)head, 1);
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 if (elem == NULL) {
99 return NULL;
100
101 }
102
103 while(elem) {
104 if ((*(head->gdCacheTest))(elem->userdata, keydata)) {
105 if (i) { /* if not already most-recently-used */
106 /* relink to top of list */
107 prev->next = elem->next;
108 elem->next = head->mru;
109 head->mru = elem;
110 }
111 return elem->userdata;
112 }
113 prevprev = prev;
114 prev = elem;
115 elem = elem->next;
116 i++;
117 }
118 userdata = (*(head->gdCacheFetch))(&(head->error), keydata);
119 if (! userdata) {
120 /* if there was an error in the fetch then don't cache */
121 return NULL;
122 }
123 if (i < head->size) { /* cache still growing - add new elem */
124 elem = (gdCache_element_t *)pemalloc(sizeof(gdCache_element_t), 1);
125 }
126 else { /* cache full - replace least-recently-used */
127 /* preveprev becomes new end of list */
128 prevprev->next = NULL;
129 elem = prev;
130 (*(head->gdCacheRelease))(elem->userdata);
131 }
132 /* relink to top of list */
133 elem->next = head->mru;
134 head->mru = elem;
135 elem->userdata = userdata;
136 return userdata;
137 }
138
139
140
141 /*********************************************************/
142 /* test stub */
143 /*********************************************************/
144
145
146 #ifdef GDCACHE_TEST
147
148 #include <stdio.h>
149
150 typedef struct {
151 int key;
152 int value;
153 } key_value_t;
154
155 static int
cacheTest(void * map,void * key)156 cacheTest( void *map, void *key )
157 {
158 return (((key_value_t *)map)->key == *(int *)key);
159 }
160
161 static void *
cacheFetch(char ** error,void * key)162 cacheFetch( char **error, void *key )
163 {
164 key_value_t *map;
165
166 map = (key_value_t *)malloc(sizeof(key_value_t));
167 if (map == NULL) {
168 return NULL;
169 }
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 free( (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
210
211 #endif /* ENABLE_GD_TTF */
212
