php-internal-docs 8.4.8
Unofficial docs for php/php-src
Loading...
Searching...
No Matches
gdcache.c
Go to the documentation of this file.
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 */
58 int size,
59 gdCacheTestFn_t gdCacheTest,
60 gdCacheFetchFn_t gdCacheFetch,
61 gdCacheReleaseFn_t gdCacheRelease)
62{
64
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
74void
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
90void *
91gdCacheGet (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
151typedef struct
152{
153 int key;
154 int value;
155}
156key_value_t;
157
158static int
159cacheTest (void *map, void *key)
160{
161 return (((key_value_t *) map)->key == *(int *) key);
162}
163
164static void *
165cacheFetch (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
177static void
178cacheRelease (void *map)
179{
180 gdFree ((char *) map);
181}
182
183int
184main (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 /* NEED_CACHE */
prev(array|object &$array)
error($message)
Definition ext_skel.php:22
new_type size
Definition ffi.c:4365
#define NULL
Definition gdcache.h:45
void(* gdCacheReleaseFn_t)(void *userdata)
Definition gdcache.h:51
void gdCacheDelete(gdCache_head_t *head)
gdCache_head_t * gdCacheCreate(int size, gdCacheTestFn_t gdCacheTest, gdCacheFetchFn_t gdCacheFetch, gdCacheReleaseFn_t gdCacheRelease)
void * gdCacheGet(gdCache_head_t *head, void *keydata)
void *(* gdCacheFetchFn_t)(char **error, void *keydata)
Definition gdcache.h:50
struct gdCache_head_s gdCache_head_t
Definition gdcache.h:61
struct gdCache_element_s gdCache_element_t
Definition gdcache.h:54
int(* gdCacheTestFn_t)(void *userdata, void *keydata)
Definition gdcache.h:49
int main(void)
Definition gddemo.c:7
#define gdPFree(ptr)
Definition gdhelpers.h:21
#define gdFree(ptr)
Definition gdhelpers.h:19
#define gdPMalloc(ptr)
Definition gdhelpers.h:20
#define gdMalloc(size)
Definition gdhelpers.h:16
struct php_pcntl_pending_signal * head
Definition php_pcntl.h:47
unsigned char key[REFLECTION_KEY_LEN]
gdCache_element_t * next
Definition gdcache.h:56
void * userdata
Definition gdcache.h:57
value