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