Annotation of embedaddon/php/ext/gd/gdcache.c, revision 1.1.1.2
1.1 misho 1: /*
1.1.1.2 ! misho 2: * $Id$
1.1 misho 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 *
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
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 *
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
151: cacheTest( void *map, void *key )
152: {
153: return (((key_value_t *)map)->key == *(int *)key);
154: }
155:
156: static void *
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
173: cacheRelease( void *map)
174: {
175: free( (char *)map );
176: }
177:
178: int
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 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>