File: cache.c

package info (click to toggle)
sn 0.3.8-12
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, buster, sid, trixie
  • size: 976 kB
  • sloc: ansic: 9,255; sh: 467; makefile: 210
file content (230 lines) | stat: -rw-r--r-- 5,307 bytes parent folder | download | duplicates (6)
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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
/*
 * This file is part of the sn package.
 * Distribution of sn is covered by the GNU GPL. See file COPYING.
 * Copyright  1998-2000 Harold Tay.
 * Copyright  2000- Patrik Rdman.
 */

/*
 * Generic caching module.  Not very sophisticated, but very heavily
 * used to avoid repeated object construction/deconstruction.
 */

#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "cache.h"

static const char ver_ctrl_id[] = "$Id: cache.c 29 2004-04-24 23:02:38Z patrik $";

/* Max number of caches (of possibly different types of object)
   that we can handle */
#ifndef CACHE_MAX
#define CACHE_MAX 4
#endif

struct entry {
   void *object;
   struct entry *prev;
   struct entry *next;
};

struct table {
   int maxsize;
   int (*cmp) (void *, void *);
   void (*freeobj) (void *);
   int (*isstale) (void *);
   struct entry *entries;
   struct entry *freelist;
   struct entry *freeblocks;
   int hit;
   int miss;
};

struct table table[CACHE_MAX] = { { 0, }, };

int cache_init (int max, int (*cmp) (void *, void *),
		         void (*freeobj) (void *),
		         int (*isstale) (void *))
{
   int i;
   int j;

   if (max <= 1 || NULL == cmp || NULL == freeobj)
   {
      errno = EINVAL;
      return -1;
   }

   for (i = 0; i < CACHE_MAX; i++)
      if (0 == table[i].maxsize)
         break;

   if (CACHE_MAX == i)
   {
      errno = ENFILE;
      return -1;
   }

   table[i].freeblocks = calloc(max, sizeof (struct entry));
   if (NULL == table[i].freeblocks)
      return -1;
   for (j = 0; j < max - 1; j++)
      table[i].freeblocks[j].next = &table[i].freeblocks[j + 1];
   table[i].freelist = table[i].freeblocks;
   table[i].maxsize = max;
   table[i].cmp = cmp;
   table[i].freeobj = freeobj;
   table[i].isstale = isstale; /* This is permitted to be NULL */
   table[i].hit = table[i].miss = 0;

   return i;
}

/* Either get a free entry from the freelist, or remove the
   last of the entries list */

static struct entry *new_entry (int desc)
{
   struct entry *ep;

   if ((ep = table[desc].freelist))
      table[desc].freelist = ep->next;
   else
   {
      for (ep = table[desc].entries; ep->next; ep = ep->next) ;
      ep->prev->next = NULL;
      table[desc].freeobj(ep->object);
   }
   ep->prev = ep->next = NULL;
   ep->object = NULL;
   return ep;
}

void cache_fin (int desc)
{
   struct entry *ep;
   struct entry *tmp;
   void (*freeobj) (void *) = table[desc].freeobj;

   for (ep = table[desc].entries; ep; ep = tmp)
   {
      (*freeobj) (ep->object);
      tmp = ep->next;
   }
   free(table[desc].freeblocks);
   memset(&table[desc], 0, sizeof (struct table));
}

void *cache_find (int desc, void *object)
{
   register struct table *tp = &table[desc];
   int (*cmp) (void *, void *) = tp->cmp;
   int (*isstale) (void *) = tp->isstale;
   struct entry *head = table[desc].entries;
   register struct entry *ep;

   for (ep = head; ep; ep = ep->next)

      if (isstale && (*isstale) (ep->object))
      {

         if (ep->prev)
            ep->prev->next = ep->next;
         else
            tp->entries = ep->next;
         if (ep->next)
            ep->next->prev = ep->prev;
         ep->next = NULL;
         (*tp->freeobj) (ep->object);
         ep->next = tp->freelist;
         tp->freelist = ep;

      }
      else if (0 == (*cmp) (object, ep->object))
      {

         /* Once found, move it to the head of the list */
         if (ep != tp->entries)
         {
            ep->prev->next = ep->next;
            if (ep->next)
               ep->next->prev = ep->prev;
            tp->entries->prev = ep;
            ep->next = tp->entries;
            tp->entries = ep;
            ep->prev = NULL;
         }
         tp->hit++;
         return tp->entries->object;
      }
   tp->miss++;
   return NULL;
}

void cache_stat (int desc, int *hit, int *miss)
{
   if (hit)
      *hit = table[desc].hit;
   if (miss)
      *miss = table[desc].miss;
}

/* Return the first item in the cache.  To be used as a hint.
   Should we be checking for staleness here? */

void *cache_top (int desc)
{
   return table[desc].entries->object;
}

/* Since new_entry() uses only pre-allocated memory, this function
   cannot fail. */

void cache_insert (int desc, void *object)
{
   register struct entry *ep;

   ep = new_entry(desc);
   ep->object = object;
   ep->next = table[desc].entries;
   if (table[desc].entries)
      table[desc].entries->prev = ep;
   table[desc].entries = ep;
}

void cache_invalidate (int desc, void *objp)
{
   struct entry *ep;
   struct entry *tmp;

   for (ep = table[desc].entries; ep; ep = tmp)
      if (0 == (*table[desc].cmp) (objp, ep->object))
      {
         if (ep->next)
            ep->next->prev = ep->prev;
         if (ep->prev)
            ep->prev->next = ep->next;
         else
            table[desc].entries = ep->next;
         (*table[desc].freeobj) (ep->object);
         tmp = ep->next;
         ep->object = NULL;
         ep->prev = NULL;
         ep->next = table[desc].freelist;
         table[desc].freelist = ep;
         break;
      }
      else
         tmp = ep->next;
}

#ifdef CACHE_DEBUG
void cache_dump (int desc, void (*printer) (void *))
{
   struct entry *ep;

   for (ep = table[desc].entries; ep; ep = ep->next)
      (*printer) (ep->object);
}
#endif /* CACHE_DEBUG */