xref: /PHP-7.1/ext/gd/gdcache.c (revision 4bebcb84)
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 #ifdef 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