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

Contents of /navit/navit/cache.c

Parent Directory Parent Directory | Revision Log Revision Log


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

   
Visit the ZANavi Wiki