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

Contents of /navit/navit/cache.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 27 - (hide annotations) (download)
Mon Apr 9 21:27:36 2012 UTC (10 years, 9 months ago) by zoff99
File MIME type: text/plain
File size: 11022 byte(s)
lots of new stuff, tranlsations, bug fixes ...
1 zoff99 27 /**
2     * ZANavi, Zoff Android Navigation system.
3     * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
4     *
5     * This program is free software; you can redistribute it and/or
6     * modify it under the terms of the GNU General Public License
7     * version 2 as published by the Free Software Foundation.
8     *
9     * This program is distributed in the hope that it will be useful,
10     * but WITHOUT ANY WARRANTY; without even the implied warranty of
11     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12     * GNU General Public License for more details.
13     *
14     * You should have received a copy of the GNU General Public License
15     * along with this program; if not, write to the
16     * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17     * Boston, MA 02110-1301, USA.
18     */
19    
20 zoff99 2 #include "glib_slice.h"
21     #ifdef DEBUG_CACHE
22     #include <stdio.h>
23     #endif
24     #include <string.h>
25     #include "debug.h"
26     #include "cache.h"
27    
28 zoff99 27 struct cache_entry
29     {
30 zoff99 2 int usage;
31     int size;
32     struct cache_entry_list *where;
33     struct cache_entry *next;
34     struct cache_entry *prev;
35     int id[0];
36     };
37    
38 zoff99 27 struct cache_entry_list
39     {
40 zoff99 2 struct cache_entry *first, *last;
41     int size;
42     };
43    
44 zoff99 27 struct cache
45     {
46     struct cache_entry_list t1, b1, t2, b2, *insert;
47     int size, id_size, entry_size;
48 zoff99 2 int t1_target;
49 zoff99 27 long misses;
50     long hits;
51 zoff99 2 GHashTable *hash;
52     };
53    
54 zoff99 27 static void cache_entry_dump(struct cache *cache, struct cache_entry *entry)
55 zoff99 2 {
56 zoff99 27 int i, size;
57     //dbg(0,"Usage: %d size %d\n",entry->usage, entry->size);
58 zoff99 2 if (cache)
59 zoff99 27 size = cache->id_size;
60 zoff99 2 else
61 zoff99 27 size = 5;
62     for (i = 0; i < size; i++)
63     {
64     dbg(0, "0x%x\n", entry->id[i]);
65 zoff99 2 }
66     }
67    
68 zoff99 27 static void cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list)
69 zoff99 2 {
70 zoff99 27 struct cache_entry *first = list->first;
71     dbg(0, "dump %s %d\n", str, list->size);
72     while (first)
73     {
74 zoff99 2 cache_entry_dump(cache, first);
75 zoff99 27 first = first->next;
76 zoff99 2 }
77     }
78    
79 zoff99 27 static guint cache_hash4(gconstpointer key)
80 zoff99 2 {
81 zoff99 27 int *id = (int *) key;
82 zoff99 2 return id[0];
83     }
84    
85 zoff99 27 static guint cache_hash20(gconstpointer key)
86 zoff99 2 {
87 zoff99 27 int *id = (int *) key;
88     return id[0] ^ id[1] ^ id[2] ^ id[3] ^ id[4];
89 zoff99 2 }
90    
91 zoff99 27 static gboolean cache_equal4(gconstpointer a, gconstpointer b)
92 zoff99 2 {
93 zoff99 27 int *ida = (int *) a;
94     int *idb = (int *) b;
95 zoff99 2
96     return ida[0] == idb[0];
97     }
98    
99 zoff99 27 static gboolean cache_equal20(gconstpointer a, gconstpointer b)
100 zoff99 2 {
101 zoff99 27 int *ida = (int *) a;
102     int *idb = (int *) b;
103 zoff99 2
104 zoff99 27 return (ida[0] == idb[0] && ida[1] == idb[1] && ida[2] == idb[2] && ida[3] == idb[3] && ida[4] == idb[4]);
105 zoff99 2 }
106    
107     struct cache *
108     cache_new(int id_size, int size)
109     {
110     struct cache *cache=g_new0(struct cache, 1);
111 zoff99 27
112     cache->id_size = id_size / 4;
113     cache->entry_size = cache->id_size * sizeof(int) + sizeof(struct cache_entry);
114     cache->size = size;
115    
116     dbg(0, "_c size=%d\n", size);
117    
118     switch (id_size)
119     {
120     case 4:
121     cache->hash = g_hash_table_new(cache_hash4, cache_equal4);
122     break;
123     case 20:
124     cache->hash = g_hash_table_new(cache_hash20, cache_equal20);
125     break;
126     default:
127     dbg(0, "cache with id_size of %d not supported\n", id_size);
128     g_free(cache);
129     cache = NULL;
130 zoff99 2 }
131     return cache;
132     }
133    
134 zoff99 27 static void cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry)
135 zoff99 2 {
136 zoff99 27 entry->prev = NULL;
137     entry->next = list->first;
138     entry->where = list;
139 zoff99 2 if (entry->next)
140 zoff99 27 entry->next->prev = entry;
141     list->first = entry;
142     if (!list->last)
143     list->last = entry;
144     list->size += entry->size;
145     if (cache)
146     g_hash_table_insert(cache->hash, (gpointer) entry->id, entry);
147 zoff99 2 }
148    
149 zoff99 27 static void cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry)
150 zoff99 2 {
151 zoff99 27 if (entry->prev)
152     entry->prev->next = entry->next;
153 zoff99 2 else
154 zoff99 27 list->first = entry->next;
155 zoff99 2 if (entry->next)
156 zoff99 27 entry->next->prev = entry->prev;
157 zoff99 2 else
158 zoff99 27 list->last = entry->prev;
159     list->size -= entry->size;
160 zoff99 2 }
161    
162 zoff99 27 static void cache_remove(struct cache *cache, struct cache_entry *entry)
163 zoff99 2 {
164 zoff99 27 // 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]);
165 zoff99 2 g_hash_table_remove(cache->hash, (gpointer)(entry->id));
166     g_slice_free1(entry->size, entry);
167     }
168    
169     static struct cache_entry *
170     cache_remove_lru_helper(struct cache_entry_list *list)
171     {
172 zoff99 27 struct cache_entry *last = list->last;
173     if (!last)
174 zoff99 2 return NULL;
175 zoff99 27 list->last = last->prev;
176 zoff99 2 if (last->prev)
177 zoff99 27 last->prev->next = NULL;
178 zoff99 2 else
179 zoff99 27 list->first = NULL;
180     list->size -= last->size;
181 zoff99 2 return last;
182     }
183    
184     static struct cache_entry *
185     cache_remove_lru(struct cache *cache, struct cache_entry_list *list)
186     {
187     struct cache_entry *last;
188 zoff99 27 int seen = 0;
189     while (list->last && list->last->usage && seen < list->size)
190     {
191     last = cache_remove_lru_helper(list);
192 zoff99 2 cache_insert_mru(NULL, list, last);
193 zoff99 27 seen += last->size;
194 zoff99 2 }
195 zoff99 27 last = list->last;
196     if (!last || last->usage || seen >= list->size)
197     {
198 zoff99 2 return NULL;
199 zoff99 27 }
200     //dbg(1,"removing %d\n", last->id[0]);
201 zoff99 2 cache_remove_lru_helper(list);
202 zoff99 27 if (cache)
203     {
204 zoff99 2 cache_remove(cache, last);
205     return NULL;
206     }
207     return last;
208     }
209    
210     void *
211     cache_entry_new(struct cache *cache, void *id, int size)
212     {
213     struct cache_entry *ret;
214 zoff99 27 size += cache->entry_size;
215     cache->misses += size;
216     ret = (struct cache_entry *) g_slice_alloc0(size);
217     ret->size = size;
218     ret->usage = 1;
219     memcpy(ret->id, id, cache->id_size * sizeof(int));
220 zoff99 2 return &ret->id[cache->id_size];
221     }
222    
223 zoff99 27 void cache_entry_destroy(struct cache *cache, void *data)
224 zoff99 2 {
225 zoff99 27 struct cache_entry *entry = (struct cache_entry *) ((char *) data - cache->entry_size);
226     // 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]);
227 zoff99 2 entry->usage--;
228     }
229    
230     static struct cache_entry *
231     cache_trim(struct cache *cache, struct cache_entry *entry)
232     {
233     struct cache_entry *new_entry;
234 zoff99 27 //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]);
235     //dbg(1,"Trim %x from %d -> %d\n", entry->id[0], entry->size, cache->size);
236     if (cache->entry_size < entry->size)
237 zoff99 2 {
238 zoff99 27 g_hash_table_remove(cache->hash, (gpointer)(entry->id));
239 zoff99 2
240 zoff99 27 new_entry = g_slice_alloc0(cache->entry_size);
241     memcpy(new_entry, entry, cache->entry_size);
242     g_slice_free1(entry->size, entry);
243     new_entry->size = cache->entry_size;
244 zoff99 2
245 zoff99 27 g_hash_table_insert(cache->hash, (gpointer) new_entry->id, new_entry);
246 zoff99 2 }
247     else
248     {
249 zoff99 27 new_entry = entry;
250 zoff99 2 }
251 zoff99 27
252 zoff99 2 return new_entry;
253     }
254    
255     static struct cache_entry *
256     cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new)
257     {
258     struct cache_entry *entry;
259 zoff99 27 entry = cache_remove_lru(NULL, old);
260     if (!entry)
261 zoff99 2 return NULL;
262 zoff99 27 entry = cache_trim(cache, entry);
263 zoff99 2 cache_insert_mru(NULL, new, entry);
264     return entry;
265     }
266    
267 zoff99 27 static int cache_replace(struct cache *cache)
268 zoff99 2 {
269 zoff99 27 if (cache->t1.size >= MAX(1, cache->t1_target))
270     {
271     //dbg(1,"replace 12\n");
272 zoff99 2 if (!cache_move(cache, &cache->t1, &cache->b1))
273     cache_move(cache, &cache->t2, &cache->b2);
274 zoff99 27 }
275     else
276     {
277     //dbg(1,"replace t2\n");
278 zoff99 2 if (!cache_move(cache, &cache->t2, &cache->b2))
279     cache_move(cache, &cache->t1, &cache->b1);
280     }
281     #if 0
282 zoff99 27 if (! entry)
283     {
284 zoff99 2 cache_dump(cache);
285     exit(0);
286     }
287     #endif
288     return 1;
289     }
290    
291 zoff99 27 void cache_flush(struct cache *cache, void *id)
292 zoff99 2 {
293 zoff99 27 struct cache_entry *entry = g_hash_table_lookup(cache->hash, id);
294     if (entry)
295     {
296 zoff99 2 cache_remove_from_list(entry->where, entry);
297     cache_remove(cache, entry);
298     }
299     }
300    
301 zoff99 27 void cache_flush_data(struct cache *cache, void *data)
302 zoff99 2 {
303 zoff99 27 struct cache_entry *entry = (struct cache_entry *) ((char *) data - cache->entry_size);
304     if (entry)
305     {
306 zoff99 2 cache_remove_from_list(entry->where, entry);
307     cache_remove(cache, entry);
308     }
309     }
310    
311     void *
312 zoff99 27 cache_lookup(struct cache *cache, void *id)
313     {
314 zoff99 2 struct cache_entry *entry;
315    
316 zoff99 27 //dbg(1,"get %d\n", ((int *)id)[0]);
317     entry = g_hash_table_lookup(cache->hash, id);
318     if (entry == NULL)
319     {
320     cache->insert = &cache->t1;
321 zoff99 2 #ifdef DEBUG_CACHE
322     fprintf(stderr,"-");
323     #endif
324 zoff99 27 //dbg(1,"not in cache\n");
325 zoff99 2 return NULL;
326     }
327 zoff99 27
328     // 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]);
329     if (entry->where == &cache->t1 || entry->where == &cache->t2)
330     {
331     cache->hits += entry->size;
332 zoff99 2 #ifdef DEBUG_CACHE
333     if (entry->where == &cache->t1)
334 zoff99 27 {
335 zoff99 2 fprintf(stderr,"h");
336 zoff99 27 }
337 zoff99 2 else
338 zoff99 27 {
339 zoff99 2 fprintf(stderr,"H");
340 zoff99 27 }
341 zoff99 2 #endif
342 zoff99 27 // dbg(1,"in cache %s\n", entry->where == &cache->t1 ? "T1" : "T2");
343 zoff99 2 cache_remove_from_list(entry->where, entry);
344     cache_insert_mru(NULL, &cache->t2, entry);
345     entry->usage++;
346     return &entry->id[cache->id_size];
347 zoff99 27 }
348     else
349     {
350     if (entry->where == &cache->b1)
351     {
352 zoff99 2 #ifdef DEBUG_CACHE
353     fprintf(stderr,"m");
354     #endif
355 zoff99 27 //dbg(1,"in phantom cache B1\n");
356     cache->t1_target = MIN(cache->t1_target + MAX(cache->b2.size / cache->b1.size, 1), cache->size);
357 zoff99 2 cache_remove_from_list(&cache->b1, entry);
358 zoff99 27 }
359     else if (entry->where == &cache->b2)
360     {
361 zoff99 2 #ifdef DEBUG_CACHE
362     fprintf(stderr,"M");
363     #endif
364 zoff99 27 //dbg(1,"in phantom cache B2\n");
365     cache->t1_target = MAX(cache->t1_target - MAX(cache->b1.size / cache->b2.size, 1), 0);
366 zoff99 2 cache_remove_from_list(&cache->b2, entry);
367     }
368 zoff99 27 else
369     {
370     //dbg(0,"**ERROR** invalid where\n");
371     }
372 zoff99 2 cache_replace(cache);
373     cache_remove(cache, entry);
374 zoff99 27 cache->insert = &cache->t2;
375 zoff99 2 return NULL;
376     }
377     }
378    
379 zoff99 27 void cache_insert(struct cache *cache, void *data)
380 zoff99 2 {
381 zoff99 27 struct cache_entry *entry = (struct cache_entry *) ((char *) data - cache->entry_size);
382     //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]);
383     if (cache->insert == &cache->t1)
384     {
385     if (cache->t1.size + cache->b1.size >= cache->size)
386     {
387     if (cache->t1.size < cache->size)
388     {
389 zoff99 2 cache_remove_lru(cache, &cache->b1);
390     cache_replace(cache);
391 zoff99 27 }
392     else
393     {
394 zoff99 2 cache_remove_lru(cache, &cache->t1);
395     }
396 zoff99 27 }
397     else
398     {
399     if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size)
400     {
401     if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2 * cache->size)
402 zoff99 2 cache_remove_lru(cache, &cache->b2);
403     cache_replace(cache);
404     }
405     }
406     }
407     cache_insert_mru(cache, cache->insert, entry);
408     }
409    
410     void *
411     cache_insert_new(struct cache *cache, void *id, int size)
412     {
413 zoff99 27 void *data = cache_entry_new(cache, id, size);
414 zoff99 2 cache_insert(cache, data);
415 zoff99 27 return data;
416 zoff99 2 }
417    
418 zoff99 27 void cache_stats(struct cache *cache)
419 zoff99 2 {
420 zoff99 27 unsigned long c_ratio = 0;
421     if ((cache->hits + cache->misses) > 0)
422     {
423     c_ratio = (long) (cache->hits) * (long) (100L);
424     //dbg(0,"1 c_ratio=%lu\n", c_ratio);
425     c_ratio = c_ratio / (long) (cache->hits + cache->misses);
426     //dbg(0,"2 c_ratio=%lu\n", c_ratio);
427    
428     dbg(0, "hits %d misses %lu hitratio %d size %d entry_size %d id_size %d T1 target %d\n", cache->hits, cache->misses, c_ratio, cache->size, cache->entry_size, cache->id_size, cache->t1_target);
429     // dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size);
430    
431     // if numbers are too big, reset them
432     if ((cache->hits > 1000000000) || (cache->misses > 1000000000))
433     {
434     cache->hits = 0;
435     cache->misses = 0;
436     }
437     }
438 zoff99 2 }
439    
440 zoff99 27 void cache_dump(struct cache *cache)
441 zoff99 2 {
442     struct cache_entry *first;
443 zoff99 27 first = cache->t1.first;
444 zoff99 2 cache_stats(cache);
445     cache_list_dump("T1", cache, &cache->t1);
446     cache_list_dump("B1", cache, &cache->b1);
447     cache_list_dump("T2", cache, &cache->t2);
448     cache_list_dump("B2", cache, &cache->b2);
449 zoff99 27 dbg(0, "dump end\n");
450 zoff99 2 }
451    

   
Visit the ZANavi Wiki