/[zanavi_public1]/navit/navit/cache.c
ZANavi

Contents of /navit/navit/cache.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2 - (show annotations) (download)
Fri Oct 28 21:19:04 2011 UTC (12 years, 5 months ago) by zoff99
File MIME type: text/plain
File size: 9661 byte(s)
import files
1 #include "glib_slice.h"
2 #ifdef DEBUG_CACHE
3 #include <stdio.h>
4 #endif
5 #include <string.h>
6 #include "debug.h"
7 #include "cache.h"
8
9 struct cache_entry {
10 int usage;
11 int size;
12 struct cache_entry_list *where;
13 struct cache_entry *next;
14 struct cache_entry *prev;
15 int id[0];
16 };
17
18 struct cache_entry_list {
19 struct cache_entry *first, *last;
20 int size;
21 };
22
23 struct cache {
24 struct cache_entry_list t1,b1,t2,b2,*insert;
25 int size,id_size,entry_size;
26 int t1_target;
27 int misses;
28 int hits;
29 GHashTable *hash;
30 };
31
32 static void
33 cache_entry_dump(struct cache *cache, struct cache_entry *entry)
34 {
35 int i,size;
36 dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
37 if (cache)
38 size=cache->id_size;
39 else
40 size=5;
41 for (i = 0 ; i < size ; i++) {
42 dbg(0,"0x%x\n", entry->id[i]);
43 }
44 }
45
46 static void
47 cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list)
48 {
49 struct cache_entry *first=list->first;
50 dbg(0,"dump %s %d\n",str, list->size);
51 while (first) {
52 cache_entry_dump(cache, first);
53 first=first->next;
54 }
55 }
56
57 static guint
58 cache_hash4(gconstpointer key)
59 {
60 int *id=(int *)key;
61 return id[0];
62 }
63
64 static guint
65 cache_hash20(gconstpointer key)
66 {
67 int *id=(int *)key;
68 return id[0]^id[1]^id[2]^id[3]^id[4];
69 }
70
71 static gboolean
72 cache_equal4(gconstpointer a, gconstpointer b)
73 {
74 int *ida=(int *)a;
75 int *idb=(int *)b;
76
77 return ida[0] == idb[0];
78 }
79
80 static gboolean
81 cache_equal20(gconstpointer a, gconstpointer b)
82 {
83 int *ida=(int *)a;
84 int *idb=(int *)b;
85
86 return(ida[0] == idb[0] &&
87 ida[1] == idb[1] &&
88 ida[2] == idb[2] &&
89 ida[3] == idb[3] &&
90 ida[4] == idb[4]);
91 }
92
93 struct cache *
94 cache_new(int id_size, int size)
95 {
96 struct cache *cache=g_new0(struct cache, 1);
97
98 cache->id_size=id_size/4;
99 cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry);
100 cache->size=size;
101 switch (id_size) {
102 case 4:
103 cache->hash=g_hash_table_new(cache_hash4, cache_equal4);
104 break;
105 case 20:
106 cache->hash=g_hash_table_new(cache_hash20, cache_equal20);
107 break;
108 default:
109 dbg(0,"cache with id_size of %d not supported\n", id_size);
110 g_free(cache);
111 cache=NULL;
112 }
113 return cache;
114 }
115
116 static void
117 cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry)
118 {
119 entry->prev=NULL;
120 entry->next=list->first;
121 entry->where=list;
122 if (entry->next)
123 entry->next->prev=entry;
124 list->first=entry;
125 if (! list->last)
126 list->last=entry;
127 list->size+=entry->size;
128 if (cache)
129 g_hash_table_insert(cache->hash, (gpointer)entry->id, entry);
130 }
131
132 static void
133 cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry)
134 {
135 if (entry->prev)
136 entry->prev->next=entry->next;
137 else
138 list->first=entry->next;
139 if (entry->next)
140 entry->next->prev=entry->prev;
141 else
142 list->last=entry->prev;
143 list->size-=entry->size;
144 }
145
146 static void
147 cache_remove(struct cache *cache, struct cache_entry *entry)
148 {
149 dbg(1,"remove 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
150 g_hash_table_remove(cache->hash, (gpointer)(entry->id));
151 g_slice_free1(entry->size, entry);
152 }
153
154 static struct cache_entry *
155 cache_remove_lru_helper(struct cache_entry_list *list)
156 {
157 struct cache_entry *last=list->last;
158 if (! last)
159 return NULL;
160 list->last=last->prev;
161 if (last->prev)
162 last->prev->next=NULL;
163 else
164 list->first=NULL;
165 list->size-=last->size;
166 return last;
167 }
168
169 static struct cache_entry *
170 cache_remove_lru(struct cache *cache, struct cache_entry_list *list)
171 {
172 struct cache_entry *last;
173 int seen=0;
174 while (list->last && list->last->usage && seen < list->size) {
175 last=cache_remove_lru_helper(list);
176 cache_insert_mru(NULL, list, last);
177 seen+=last->size;
178 }
179 last=list->last;
180 if (! last || last->usage || seen >= list->size)
181 return NULL;
182 dbg(1,"removing %d\n", last->id[0]);
183 cache_remove_lru_helper(list);
184 if (cache) {
185 cache_remove(cache, last);
186 return NULL;
187 }
188 return last;
189 }
190
191 void *
192 cache_entry_new(struct cache *cache, void *id, int size)
193 {
194 struct cache_entry *ret;
195 size+=cache->entry_size;
196 cache->misses+=size;
197 ret=(struct cache_entry *)g_slice_alloc0(size);
198 ret->size=size;
199 ret->usage=1;
200 memcpy(ret->id, id, cache->id_size*sizeof(int));
201 return &ret->id[cache->id_size];
202 }
203
204 void
205 cache_entry_destroy(struct cache *cache, void *data)
206 {
207 struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
208 dbg(1,"destroy 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
209 entry->usage--;
210 }
211
212 static struct cache_entry *
213 cache_trim(struct cache *cache, struct cache_entry *entry)
214 {
215 struct cache_entry *new_entry;
216 dbg(1,"trim 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
217 dbg(1,"Trim %x from %d -> %d\n", entry->id[0], entry->size, cache->size);
218 if ( cache->entry_size < entry->size )
219 {
220 g_hash_table_remove(cache->hash, (gpointer)(entry->id));
221
222 new_entry = g_slice_alloc0(cache->entry_size);
223 memcpy(new_entry, entry, cache->entry_size);
224 g_slice_free1( entry->size, entry);
225 new_entry->size = cache->entry_size;
226
227 g_hash_table_insert(cache->hash, (gpointer)new_entry->id, new_entry);
228 }
229 else
230 {
231 new_entry = entry;
232 }
233
234 return new_entry;
235 }
236
237 static struct cache_entry *
238 cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new)
239 {
240 struct cache_entry *entry;
241 entry=cache_remove_lru(NULL, old);
242 if (! entry)
243 return NULL;
244 entry=cache_trim(cache, entry);
245 cache_insert_mru(NULL, new, entry);
246 return entry;
247 }
248
249 static int
250 cache_replace(struct cache *cache)
251 {
252 if (cache->t1.size >= MAX(1,cache->t1_target)) {
253 dbg(1,"replace 12\n");
254 if (!cache_move(cache, &cache->t1, &cache->b1))
255 cache_move(cache, &cache->t2, &cache->b2);
256 } else {
257 dbg(1,"replace t2\n");
258 if (!cache_move(cache, &cache->t2, &cache->b2))
259 cache_move(cache, &cache->t1, &cache->b1);
260 }
261 #if 0
262 if (! entry) {
263 cache_dump(cache);
264 exit(0);
265 }
266 #endif
267 return 1;
268 }
269
270 void
271 cache_flush(struct cache *cache, void *id)
272 {
273 struct cache_entry *entry=g_hash_table_lookup(cache->hash, id);
274 if (entry) {
275 cache_remove_from_list(entry->where, entry);
276 cache_remove(cache, entry);
277 }
278 }
279
280 void
281 cache_flush_data(struct cache *cache, void *data)
282 {
283 struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
284 if (entry) {
285 cache_remove_from_list(entry->where, entry);
286 cache_remove(cache, entry);
287 }
288 }
289
290
291 void *
292 cache_lookup(struct cache *cache, void *id) {
293 struct cache_entry *entry;
294
295 dbg(1,"get %d\n", ((int *)id)[0]);
296 entry=g_hash_table_lookup(cache->hash, id);
297 if (entry == NULL) {
298 cache->insert=&cache->t1;
299 #ifdef DEBUG_CACHE
300 fprintf(stderr,"-");
301 #endif
302 dbg(1,"not in cache\n");
303 return NULL;
304 }
305 dbg(1,"found 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
306 if (entry->where == &cache->t1 || entry->where == &cache->t2) {
307 cache->hits+=entry->size;
308 #ifdef DEBUG_CACHE
309 if (entry->where == &cache->t1)
310 fprintf(stderr,"h");
311 else
312 fprintf(stderr,"H");
313 #endif
314 dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
315 cache_remove_from_list(entry->where, entry);
316 cache_insert_mru(NULL, &cache->t2, entry);
317 entry->usage++;
318 return &entry->id[cache->id_size];
319 } else {
320 if (entry->where == &cache->b1) {
321 #ifdef DEBUG_CACHE
322 fprintf(stderr,"m");
323 #endif
324 dbg(1,"in phantom cache B1\n");
325 cache->t1_target=MIN(cache->t1_target+MAX(cache->b2.size/cache->b1.size, 1),cache->size);
326 cache_remove_from_list(&cache->b1, entry);
327 } else if (entry->where == &cache->b2) {
328 #ifdef DEBUG_CACHE
329 fprintf(stderr,"M");
330 #endif
331 dbg(1,"in phantom cache B2\n");
332 cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0);
333 cache_remove_from_list(&cache->b2, entry);
334 } else {
335 dbg(0,"**ERROR** invalid where\n");
336 }
337 cache_replace(cache);
338 cache_remove(cache, entry);
339 cache->insert=&cache->t2;
340 return NULL;
341 }
342 }
343
344 void
345 cache_insert(struct cache *cache, void *data)
346 {
347 struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size);
348 dbg(1,"insert 0x%x 0x%x 0x%x 0x%x 0x%x\n", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]);
349 if (cache->insert == &cache->t1) {
350 if (cache->t1.size + cache->b1.size >= cache->size) {
351 if (cache->t1.size < cache->size) {
352 cache_remove_lru(cache, &cache->b1);
353 cache_replace(cache);
354 } else {
355 cache_remove_lru(cache, &cache->t1);
356 }
357 } else {
358 if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) {
359 if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size)
360 cache_remove_lru(cache, &cache->b2);
361 cache_replace(cache);
362 }
363 }
364 }
365 cache_insert_mru(cache, cache->insert, entry);
366 }
367
368 void *
369 cache_insert_new(struct cache *cache, void *id, int size)
370 {
371 void *data=cache_entry_new(cache, id, size);
372 cache_insert(cache, data);
373 return data;
374 }
375
376 static void
377 cache_stats(struct cache *cache)
378 {
379 dbg(0,"hits %d misses %d hitratio %d size %d entry_size %d id_size %d T1 target %d\n", cache->hits, cache->misses, cache->hits*100/(cache->hits+cache->misses), cache->size, cache->entry_size, cache->id_size, cache->t1_target);
380 dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);
381 cache->hits=0;
382 cache->misses=0;
383 }
384
385 void
386 cache_dump(struct cache *cache)
387 {
388 struct cache_entry *first;
389 first=cache->t1.first;
390 cache_stats(cache);
391 cache_list_dump("T1", cache, &cache->t1);
392 cache_list_dump("B1", cache, &cache->b1);
393 cache_list_dump("T2", cache, &cache->t2);
394 cache_list_dump("B2", cache, &cache->b2);
395 dbg(0,"dump end\n");
396 }
397

   
Visit the ZANavi Wiki