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_CACHE_CREATE)
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 while(elem) {
99 if ((*(head->gdCacheTest))(elem->userdata, keydata)) {
100 if (i) { /* if not already most-recently-used */
101 /* relink to top of list */
102 prev->next = elem->next;
103 elem->next = head->mru;
104 head->mru = elem;
105 }
106 return elem->userdata;
107 }
108 prevprev = prev;
109 prev = elem;
110 elem = elem->next;
111 i++;
112 }
113 userdata = (*(head->gdCacheFetch))(&(head->error), keydata);
114 if (! userdata) {
115 /* if there was an error in the fetch then don't cache */
116 return NULL;
117 }
118 if (i < head->size) { /* cache still growing - add new elem */
119 elem = (gdCache_element_t *)pemalloc(sizeof(gdCache_element_t), 1);
120 }
121 else { /* cache full - replace least-recently-used */
122 /* preveprev becomes new end of list */
123 prevprev->next = NULL;
124 elem = prev;
125 (*(head->gdCacheRelease))(elem->userdata);
126 }
127 /* relink to top of list */
128 elem->next = head->mru;
129 head->mru = elem;
130 elem->userdata = userdata;
131 return userdata;
132 }
133
134
135
136 /*********************************************************/
137 /* test stub */
138 /*********************************************************/
139
140
141 #ifdef GDCACHE_TEST
142
143 #include <stdio.h>
144
145 typedef struct {
146 int key;
147 int value;
148 } key_value_t;
149
150 static int
cacheTest(void * map,void * key)151 cacheTest( void *map, void *key )
152 {
153 return (((key_value_t *)map)->key == *(int *)key);
154 }
155
156 static void *
cacheFetch(char ** error,void * key)157 cacheFetch( char **error, void *key )
158 {
159 key_value_t *map;
160
161 map = (key_value_t *)malloc(sizeof(key_value_t));
162 if (map == NULL) {
163 return NULL;
164 }
165 map->key = *(int *)key;
166 map->value = 3;
167
168 *error = NULL;
169 return (void *)map;
170 }
171
172 static void
cacheRelease(void * map)173 cacheRelease( void *map)
174 {
175 free( (char *)map );
176 }
177
178 int
main(char * argv[],int argc)179 main(char *argv[], int argc)
180 {
181 gdCache_head_t *cacheTable;
182 int elem, key;
183
184 cacheTable = gdCacheCreate(3, cacheTest, cacheFetch, cacheRelease);
185
186 key = 20;
187 elem = *(int *)gdCacheGet(cacheTable, &key);
188 key = 30;
189 elem = *(int *)gdCacheGet(cacheTable, &key);
190 key = 40;
191 elem = *(int *)gdCacheGet(cacheTable, &key);
192 key = 50;
193 elem = *(int *)gdCacheGet(cacheTable, &key);
194 key = 30;
195 elem = *(int *)gdCacheGet(cacheTable, &key);
196 key = 30;
197 elem = *(int *)gdCacheGet(cacheTable, &key);
198
199 gdCacheDelete(cacheTable);
200
201 return 0;
202 }
203
204 #endif
205
206 #endif /* ENABLE_GD_TTF */
207
