1 /*
2 * Simple FIFO generic cache. (c) Radim Kolar 2003, 2009
3 * This file is copyrighted as LGPL v2.1
4 *
5 * When this file is used as part of FSP, it uses 2-term BSD license
6 * (aka MIT/X11 License).
7 */
8
9 #include <stdlib.h>
10 #include <string.h>
11 #include <stdio.h>
12 #include "fifocache.h"
13
14 /**
15 * Create new FIFO cache.
16 *
17 * Allocates a memory for new cache stucture and initialise it.
18 *
19 * @param cachesize cache size in number of entries
20 * @param entrysize size of one entry in bytes
21 * @param edf entry destroy function
22 * @param kdf key destroy function
23 * @param kcf key compare function, must return zero for equals keys
24 * @return NULL or error, otherwise newly allocated fifocache structure
25 */
26
f_cache_new(unsigned int cachesize,unsigned int entrysize,void (* edf)(void *),unsigned int keysize,void (* kdf)(void *),int (* kcf)(const void *,const void *))27 struct FifoCache * f_cache_new(unsigned int cachesize,unsigned int entrysize,
28 void (*edf) (void *),unsigned int keysize, void (*kdf) (void *), int (*kcf)(const void *,const void *))
29 {
30 struct FifoCache *cache;
31 if(cachesize==0) return NULL;
32 if(entrysize==0 && keysize==0) return NULL;
33 cache=calloc(1,sizeof(struct FifoCache));
34 if(cache==NULL) return NULL;
35
36 cache->cachesize=cachesize;
37 cache->keysize=keysize;
38 cache->entrysize=entrysize;
39
40 if(entrysize==0)
41 cache->e_head=calloc(1,1);
42 else
43 cache->e_head=calloc(cachesize,entrysize);
44
45 if(keysize==0)
46 cache->k_head=calloc(1,1);
47 else
48 cache->k_head=calloc(cachesize,keysize);
49
50 if(!cache->e_head || !cache->k_head)
51 {
52 f_cache_destroy(cache);
53 return NULL;
54 }
55 cache->k_next=cache->k_head;
56
57 if(keysize==0)
58 cache->k_stop=NULL;
59 else
60 cache->k_stop=cache->k_head+cache->keysize*cache->cachesize;
61
62 cache->e_next=cache->e_head;
63 if(entrysize==0)
64 cache->e_stop=NULL;
65 else
66 cache->e_stop=cache->e_head+cache->entrysize*cache->cachesize;
67
68 cache->k_destroy_func=kdf;
69 cache->e_destroy_func=edf;
70 cache->k_compare_func=kcf;
71
72 return cache;
73 }
74
75 /**
76 * Set memory profile functions.
77 *
78 * Memory profile functions returns sizes of data referenced
79 * by keys or entries. In this cache entries and keys are fixed
80 * size.
81 *
82 * @param cache cache to operate on
83 * @param keysize returns size of key in bytes
84 * @param entrysize returns size of entry in bytes
85 */
f_cache_set_memory_profilers(struct FifoCache * cache,unsigned int (* keysize)(const void * key),unsigned int (* entrysize)(const void * entry))86 void f_cache_set_memory_profilers(struct FifoCache *cache,unsigned int (*keysize) (const void *key),unsigned int (*entrysize) (const void *entry))
87 {
88 cache->get_keysize=keysize;
89 cache->get_entrysize=entrysize;
90 }
91
92 /**
93 * Prints cache memory usage and hit/miss ratio.
94 *
95 * @param cache cache to operate on
96 * @param f FILE to write results to
97 */
f_cache_stats(struct FifoCache * cache,FILE * f)98 void f_cache_stats(struct FifoCache *cache,FILE *f)
99 {
100 unsigned int i;
101 unsigned int used=0;
102 unsigned int j;
103 unsigned int dkey=0;
104 unsigned int dentry=0;
105
106 if(f==NULL) return;
107 /* count used items */
108 for(i=0;i<cache->cachesize;i++)
109 {
110 if(cache->keysize>0)
111 {
112 for(j=0;j<cache->keysize;j++)
113 {
114 if( *(const char*)(cache->k_head+i*cache->keysize+j) != 0)
115 {
116 used++;
117 break;
118 }
119 }
120 }
121 }
122
123 /* calculate dynamic memory used */
124 if(cache->get_keysize)
125 {
126 for(i=0;i<cache->cachesize;i++)
127 {
128 dkey+=cache->get_keysize(cache->k_head+i*cache->keysize);
129 }
130 }
131 if(cache->get_entrysize)
132 {
133 for(i=0;i<cache->cachesize;i++)
134 {
135 dentry+=cache->get_entrysize(cache->e_head+i*cache->entrysize);
136 }
137 }
138 fprintf(f,"%u entries (%u used). Memory: %u hdr, keys %u static + %u dynamic, entries %u static + %u dynamic. Hit ratio: %u hit, %u miss.\n",
139 cache->cachesize,used,(unsigned int)sizeof(struct FifoCache), cache->cachesize*cache->keysize,dkey,cache->cachesize*cache->entrysize,dentry,cache->hit,cache->miss);
140 }
141
142 /**
143 * Empty memory profiler function.
144 *
145 * Intended use is passing this function as argument to
146 * f_cache_set_memory_profilers.
147 *
148 * @return always 0
149 */
f_cache_void_profiler(void * anything)150 unsigned int f_cache_void_profiler(void *anything)
151 {
152 return 0;
153 }
154
155 /**
156 * Destroys cache without calling destructor function on
157 * keys or elements.
158 *
159 * Keys and elements and cache control structure are zeroed and deallocated
160 * but if they pointed to another structures via pointers, then these
161 * structures are left intact.
162 *
163 * @param cache cache to be destroyed
164 */
f_cache_destroy(struct FifoCache * cache)165 void f_cache_destroy(struct FifoCache *cache)
166 {
167 if(cache==NULL) return;
168 if(cache->e_head)
169 {
170 memset(cache->e_head,0,cache->entrysize*cache->cachesize);
171 free(cache->e_head);
172 }
173 if(cache->k_head) {
174 memset(cache->k_head,0,cache->keysize*cache->cachesize);
175 free(cache->k_head);
176 }
177 memset(cache,0,sizeof(struct FifoCache));
178 free(cache);
179 }
180
181 /**
182 * Copy record into cache replacing existing record.
183 *
184 * Always creates new record even if we already have record for key in
185 * cache.
186 * @param cache cache to put record into
187 * @param key key for record
188 * @param data data for record
189 * @return pointer to data entry in cache
190 */
f_cache_put(struct FifoCache * cache,const void * key,const void * data)191 void * f_cache_put(struct FifoCache *cache,const void *key,const void *data)
192 {
193 void *where;
194 /* free place for new element */
195 if(cache->k_destroy_func) cache->k_destroy_func(cache->k_next);
196 if(cache->e_destroy_func) cache->e_destroy_func(cache->e_next);
197
198 /* copy new element in */
199 where=cache->e_next;
200 memcpy(cache->k_next,key,cache->keysize);
201 memcpy(cache->e_next,data,cache->entrysize);
202
203 /* update next pos. */
204 cache->e_next+=cache->entrysize;
205 cache->k_next+=cache->keysize;
206
207 /* roll over? */
208 if(cache->e_next==cache->e_stop || cache->k_next==cache->k_stop)
209 {
210 cache->e_next=cache->e_head;
211 cache->k_next=cache->k_head;
212 }
213
214 return where;
215 }
216
217 /**
218 * Find element by key.
219 *
220 * Linear search is performed.
221 * @param cache used cache
222 * @param key key for finding data
223 * @return cached data or NULL
224 */
f_cache_find(struct FifoCache * cache,const void * key)225 void *f_cache_find(struct FifoCache *cache,const void *key)
226 {
227 unsigned int i;
228
229 if(!cache->k_compare_func) return NULL;
230 if(cache->keysize==0) return NULL;
231
232 for(i=0;i<cache->cachesize;i++)
233 {
234 if(!cache->k_compare_func(key,cache->k_head+i*cache->keysize))
235 {
236 cache->hit++;
237 return cache->e_head+i*cache->entrysize;
238 }
239 }
240 cache->miss++;
241 return NULL;
242 }
243
244 /**
245 * clear all elements from the cache.
246 *
247 * Cache itself is not destroyed and destroy functions are called.
248 *
249 * @param cache cache to be cleared
250 */
f_cache_clear(struct FifoCache * cache)251 void f_cache_clear(struct FifoCache *cache)
252 {
253 unsigned int i;
254
255 /* free entries */
256 for(i=0;i<cache->cachesize;i++)
257 {
258 if(cache->k_destroy_func)
259 cache->k_destroy_func(cache->k_head+i*cache->keysize);
260 if(cache->e_destroy_func)
261 cache->e_destroy_func(cache->e_head+i*cache->entrysize);
262 }
263
264 /* clear entries */
265 memset(cache->k_head,0,cache->cachesize*cache->keysize);
266 memset(cache->e_head,0,cache->cachesize*cache->entrysize);
267
268 cache->k_next=cache->k_head;
269 cache->e_next=cache->e_head;
270
271 cache->hit=0;
272 cache->miss=0;
273 }
274
275 /**
276 * find key for given entry.
277 *
278 * Entry must been received from cache before. We also dont
279 * check if data have not been overwriten by new content after receiving.
280 *
281 * @param cache cache to search
282 * @param entry entry to search
283 * @return key for entry or NULL
284 */
f_cache_get_key(struct FifoCache * cache,const void * entry)285 void * f_cache_get_key(struct FifoCache *cache,const void *entry)
286 {
287 unsigned int i;
288 if(cache->entrysize==0 || cache->keysize==0) return NULL;
289
290 /* check if pointer is good */
291 if(entry<(const void *)cache->e_head || entry>=(const void *)cache->e_stop)
292 return NULL;
293 /* find cache index */
294 i=((const int8_t *)entry-cache->e_head)/cache->entrysize;
295 return cache->k_head+cache->keysize*i;
296 }
297
298 /**
299 * delete entry from cache.
300 *
301 * Destroy function is called on entry.
302 * @param cache from what cache to delete entry
303 * @param entry entry to be deleted
304 * @return one if object is deleted
305 */
f_cache_delete_entry(struct FifoCache * cache,void * entry)306 int f_cache_delete_entry(struct FifoCache *cache, void *entry)
307 {
308 unsigned int i;
309
310 if(cache->entrysize==0) return 0;
311 /* check if pointer is good */
312 if(entry<(const void *)cache->e_head || entry>=(const void *)cache->e_stop) return 0;
313 /* find cache index */
314 i=((int8_t *)entry-cache->e_head)/cache->entrysize;
315
316 /* deallocate */
317 if(cache->k_destroy_func) cache->k_destroy_func(cache->k_head+cache->keysize*i);
318 if(cache->e_destroy_func) cache->e_destroy_func(entry);
319 /* zero them */
320 memset(entry,0,cache->entrysize);
321 memset(cache->k_head+cache->keysize*i,0,cache->keysize);
322
323 return 1;
324 }
325
326 /**
327 * Perform searched delete
328 *
329 * @param cache cache to search
330 * @param key key used for deleting entries
331 * @return how many objects were deleted.
332 */
f_cache_delete_by_key(struct FifoCache * cache,void * key)333 int f_cache_delete_by_key(struct FifoCache *cache, void *key)
334 {
335 unsigned int i;
336 int deleted=0;
337
338 if(!cache->k_compare_func) return 0;
339
340 for(i=0;i<cache->cachesize;i++)
341 {
342 if(!cache->k_compare_func(key,cache->k_head+i*cache->keysize))
343 {
344 deleted+=f_cache_delete_entry(cache,cache->e_head+i*cache->entrysize);
345 }
346 }
347
348 return deleted;
349 }
350