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

Contents of /navit/navit/cache.c

Parent Directory Parent Directory | Revision Log Revision Log


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

   
Visit the ZANavi Wiki