xref: /PHP-5.4/ext/gd/gdcache.c (revision c278fb01)
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