← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to gd/gdcache.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

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