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