diff options
Diffstat (limited to 'navit/cache.c')
-rw-r--r-- | navit/cache.c | 564 |
1 files changed, 269 insertions, 295 deletions
diff --git a/navit/cache.c b/navit/cache.c index 6c618c9fc..c52335989 100644 --- a/navit/cache.c +++ b/navit/cache.c @@ -7,395 +7,369 @@ #include "cache.h" struct cache_entry { - int usage; - unsigned int size; - struct cache_entry_list *where; - struct cache_entry *next; - struct cache_entry *prev; - int id[0]; + int usage; + unsigned int size; + struct cache_entry_list *where; + struct cache_entry *next; + struct cache_entry *prev; + int id[0]; }; struct cache_entry_list { - struct cache_entry *first, *last; - int size; + struct cache_entry *first, *last; + int size; }; struct cache { - struct cache_entry_list t1,b1,t2,b2,*insert; - int size,id_size,entry_size; - int t1_target; - unsigned int misses; - unsigned int hits; - GHashTable *hash; + struct cache_entry_list t1,b1,t2,b2,*insert; + int size,id_size,entry_size; + int t1_target; + unsigned int misses; + unsigned int hits; + GHashTable *hash; }; static void -cache_entry_dump(struct cache *cache, struct cache_entry *entry) -{ - int i,size; - dbg(lvl_debug,"Usage: %d size %d",entry->usage, entry->size); - if (cache) - size=cache->id_size; - else - size=5; - for (i = 0 ; i < size ; i++) { - dbg(lvl_debug,"0x%x", entry->id[i]); - } +cache_entry_dump(struct cache *cache, struct cache_entry *entry) { + int i,size; + dbg(lvl_debug,"Usage: %d size %d",entry->usage, entry->size); + if (cache) + size=cache->id_size; + else + size=5; + for (i = 0 ; i < size ; i++) { + dbg(lvl_debug,"0x%x", entry->id[i]); + } } static void -cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list) -{ - struct cache_entry *first=list->first; - dbg(lvl_debug,"dump %s %d",str, list->size); - while (first) { - cache_entry_dump(cache, first); - first=first->next; - } +cache_list_dump(char *str, struct cache *cache, struct cache_entry_list *list) { + struct cache_entry *first=list->first; + dbg(lvl_debug,"dump %s %d",str, list->size); + while (first) { + cache_entry_dump(cache, first); + first=first->next; + } } static guint -cache_hash4(gconstpointer key) -{ - int *id=(int *)key; - return id[0]; +cache_hash4(gconstpointer key) { + int *id=(int *)key; + return id[0]; } static guint -cache_hash20(gconstpointer key) -{ - int *id=(int *)key; - return id[0]^id[1]^id[2]^id[3]^id[4]; +cache_hash20(gconstpointer key) { + int *id=(int *)key; + return id[0]^id[1]^id[2]^id[3]^id[4]; } static gboolean -cache_equal4(gconstpointer a, gconstpointer b) -{ - int *ida=(int *)a; - int *idb=(int *)b; +cache_equal4(gconstpointer a, gconstpointer b) { + int *ida=(int *)a; + int *idb=(int *)b; - return ida[0] == idb[0]; + return ida[0] == idb[0]; } static gboolean -cache_equal20(gconstpointer a, gconstpointer b) -{ - int *ida=(int *)a; - int *idb=(int *)b; - - return(ida[0] == idb[0] && - ida[1] == idb[1] && - ida[2] == idb[2] && - ida[3] == idb[3] && - ida[4] == idb[4]); +cache_equal20(gconstpointer a, gconstpointer b) { + int *ida=(int *)a; + int *idb=(int *)b; + + return(ida[0] == idb[0] && + ida[1] == idb[1] && + ida[2] == idb[2] && + ida[3] == idb[3] && + ida[4] == idb[4]); } struct cache * -cache_new(int id_size, int size) -{ - struct cache *cache=g_new0(struct cache, 1); - - cache->id_size=id_size/4; - cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry); - cache->size=size; - switch (id_size) { - case 4: - cache->hash=g_hash_table_new(cache_hash4, cache_equal4); - break; - case 20: - cache->hash=g_hash_table_new(cache_hash20, cache_equal20); - break; - default: - dbg(lvl_error,"cache with id_size of %d not supported", id_size); - g_free(cache); - cache=NULL; - } - return cache; +cache_new(int id_size, int size) { + struct cache *cache=g_new0(struct cache, 1); + + cache->id_size=id_size/4; + cache->entry_size=cache->id_size*sizeof(int)+sizeof(struct cache_entry); + cache->size=size; + switch (id_size) { + case 4: + cache->hash=g_hash_table_new(cache_hash4, cache_equal4); + break; + case 20: + cache->hash=g_hash_table_new(cache_hash20, cache_equal20); + break; + default: + dbg(lvl_error,"cache with id_size of %d not supported", id_size); + g_free(cache); + cache=NULL; + } + return cache; } void -cache_resize(struct cache *cache, int size) -{ - cache->size=size; +cache_resize(struct cache *cache, int size) { + cache->size=size; } static void -cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry) -{ - entry->prev=NULL; - entry->next=list->first; - entry->where=list; - if (entry->next) - entry->next->prev=entry; - list->first=entry; - if (! list->last) - list->last=entry; - list->size+=entry->size; - if (cache) - g_hash_table_insert(cache->hash, (gpointer)entry->id, entry); +cache_insert_mru(struct cache *cache, struct cache_entry_list *list, struct cache_entry *entry) { + entry->prev=NULL; + entry->next=list->first; + entry->where=list; + if (entry->next) + entry->next->prev=entry; + list->first=entry; + if (! list->last) + list->last=entry; + list->size+=entry->size; + if (cache) + g_hash_table_insert(cache->hash, (gpointer)entry->id, entry); } static void -cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry) -{ - if (entry->prev) - entry->prev->next=entry->next; - else - list->first=entry->next; - if (entry->next) - entry->next->prev=entry->prev; - else - list->last=entry->prev; - list->size-=entry->size; +cache_remove_from_list(struct cache_entry_list *list, struct cache_entry *entry) { + if (entry->prev) + entry->prev->next=entry->next; + else + list->first=entry->next; + if (entry->next) + entry->next->prev=entry->prev; + else + list->last=entry->prev; + list->size-=entry->size; } static void -cache_remove(struct cache *cache, struct cache_entry *entry) -{ - dbg(lvl_debug,"remove 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); - g_hash_table_remove(cache->hash, (gpointer)(entry->id)); - g_slice_free1(entry->size, entry); +cache_remove(struct cache *cache, struct cache_entry *entry) { + dbg(lvl_debug,"remove 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); + g_hash_table_remove(cache->hash, (gpointer)(entry->id)); + g_slice_free1(entry->size, entry); } static struct cache_entry * -cache_remove_lru_helper(struct cache_entry_list *list) -{ - struct cache_entry *last=list->last; - if (! last) - return NULL; - list->last=last->prev; - if (last->prev) - last->prev->next=NULL; - else - list->first=NULL; - list->size-=last->size; - return last; +cache_remove_lru_helper(struct cache_entry_list *list) { + struct cache_entry *last=list->last; + if (! last) + return NULL; + list->last=last->prev; + if (last->prev) + last->prev->next=NULL; + else + list->first=NULL; + list->size-=last->size; + return last; } static struct cache_entry * -cache_remove_lru(struct cache *cache, struct cache_entry_list *list) -{ - struct cache_entry *last; - int seen=0; - while (list->last && list->last->usage && seen < list->size) { - last=cache_remove_lru_helper(list); - cache_insert_mru(NULL, list, last); - seen+=last->size; - } - last=list->last; - if (! last || last->usage || seen >= list->size) - return NULL; - dbg(lvl_debug,"removing %d", last->id[0]); - cache_remove_lru_helper(list); - if (cache) { - cache_remove(cache, last); - return NULL; - } - return last; +cache_remove_lru(struct cache *cache, struct cache_entry_list *list) { + struct cache_entry *last; + int seen=0; + while (list->last && list->last->usage && seen < list->size) { + last=cache_remove_lru_helper(list); + cache_insert_mru(NULL, list, last); + seen+=last->size; + } + last=list->last; + if (! last || last->usage || seen >= list->size) + return NULL; + dbg(lvl_debug,"removing %d", last->id[0]); + cache_remove_lru_helper(list); + if (cache) { + cache_remove(cache, last); + return NULL; + } + return last; } void * -cache_entry_new(struct cache *cache, void *id, int size) -{ - struct cache_entry *ret; - size+=cache->entry_size; - cache->misses+=size; - ret=(struct cache_entry *)g_slice_alloc0(size); - ret->size=size; - ret->usage=1; - memcpy(ret->id, id, cache->id_size*sizeof(int)); - return &ret->id[cache->id_size]; +cache_entry_new(struct cache *cache, void *id, int size) { + struct cache_entry *ret; + size+=cache->entry_size; + cache->misses+=size; + ret=(struct cache_entry *)g_slice_alloc0(size); + ret->size=size; + ret->usage=1; + memcpy(ret->id, id, cache->id_size*sizeof(int)); + return &ret->id[cache->id_size]; } void -cache_entry_destroy(struct cache *cache, void *data) -{ - struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); - dbg(lvl_debug,"destroy 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); - entry->usage--; +cache_entry_destroy(struct cache *cache, void *data) { + struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); + dbg(lvl_debug,"destroy 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); + entry->usage--; } static struct cache_entry * -cache_trim(struct cache *cache, struct cache_entry *entry) -{ - struct cache_entry *new_entry; - dbg(lvl_debug,"trim 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); - dbg(lvl_debug,"Trim %x from %d -> %d", entry->id[0], entry->size, cache->size); - if ( cache->entry_size < entry->size ) - { - g_hash_table_remove(cache->hash, (gpointer)(entry->id)); - - new_entry = g_slice_alloc0(cache->entry_size); - memcpy(new_entry, entry, cache->entry_size); - g_slice_free1( entry->size, entry); - new_entry->size = cache->entry_size; - - g_hash_table_insert(cache->hash, (gpointer)new_entry->id, new_entry); - } - else - { - new_entry = entry; - } - - return new_entry; +cache_trim(struct cache *cache, struct cache_entry *entry) { + struct cache_entry *new_entry; + dbg(lvl_debug,"trim 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); + dbg(lvl_debug,"Trim %x from %d -> %d", entry->id[0], entry->size, cache->size); + if ( cache->entry_size < entry->size ) { + g_hash_table_remove(cache->hash, (gpointer)(entry->id)); + + new_entry = g_slice_alloc0(cache->entry_size); + memcpy(new_entry, entry, cache->entry_size); + g_slice_free1( entry->size, entry); + new_entry->size = cache->entry_size; + + g_hash_table_insert(cache->hash, (gpointer)new_entry->id, new_entry); + } else { + new_entry = entry; + } + + return new_entry; } static struct cache_entry * -cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new) -{ - struct cache_entry *entry; - entry=cache_remove_lru(NULL, old); - if (! entry) - return NULL; - entry=cache_trim(cache, entry); - cache_insert_mru(NULL, new, entry); - return entry; +cache_move(struct cache *cache, struct cache_entry_list *old, struct cache_entry_list *new) { + struct cache_entry *entry; + entry=cache_remove_lru(NULL, old); + if (! entry) + return NULL; + entry=cache_trim(cache, entry); + cache_insert_mru(NULL, new, entry); + return entry; } static int -cache_replace(struct cache *cache) -{ - if (cache->t1.size >= MAX(1,cache->t1_target)) { - dbg(lvl_debug,"replace 12"); - if (!cache_move(cache, &cache->t1, &cache->b1)) - cache_move(cache, &cache->t2, &cache->b2); - } else { - dbg(lvl_debug,"replace t2"); - if (!cache_move(cache, &cache->t2, &cache->b2)) - cache_move(cache, &cache->t1, &cache->b1); - } +cache_replace(struct cache *cache) { + if (cache->t1.size >= MAX(1,cache->t1_target)) { + dbg(lvl_debug,"replace 12"); + if (!cache_move(cache, &cache->t1, &cache->b1)) + cache_move(cache, &cache->t2, &cache->b2); + } else { + dbg(lvl_debug,"replace t2"); + if (!cache_move(cache, &cache->t2, &cache->b2)) + cache_move(cache, &cache->t1, &cache->b1); + } #if 0 - if (! entry) { - cache_dump(cache); - exit(0); - } + if (! entry) { + cache_dump(cache); + exit(0); + } #endif - return 1; + return 1; } void -cache_flush(struct cache *cache, void *id) -{ - struct cache_entry *entry=g_hash_table_lookup(cache->hash, id); - if (entry) { - cache_remove_from_list(entry->where, entry); - cache_remove(cache, entry); - } +cache_flush(struct cache *cache, void *id) { + struct cache_entry *entry=g_hash_table_lookup(cache->hash, id); + if (entry) { + cache_remove_from_list(entry->where, entry); + cache_remove(cache, entry); + } } void -cache_flush_data(struct cache *cache, void *data) -{ - struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); - if (entry) { - cache_remove_from_list(entry->where, entry); - cache_remove(cache, entry); - } +cache_flush_data(struct cache *cache, void *data) { + struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); + if (entry) { + cache_remove_from_list(entry->where, entry); + cache_remove(cache, entry); + } } void * cache_lookup(struct cache *cache, void *id) { - struct cache_entry *entry; + struct cache_entry *entry; - dbg(lvl_debug,"get %d", ((int *)id)[0]); - entry=g_hash_table_lookup(cache->hash, id); - if (entry == NULL) { - cache->insert=&cache->t1; + dbg(lvl_debug,"get %d", ((int *)id)[0]); + entry=g_hash_table_lookup(cache->hash, id); + if (entry == NULL) { + cache->insert=&cache->t1; #ifdef DEBUG_CACHE - fprintf(stderr,"-"); + fprintf(stderr,"-"); #endif - dbg(lvl_debug,"not in cache"); - return NULL; - } - dbg(lvl_debug,"found 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); - if (entry->where == &cache->t1 || entry->where == &cache->t2) { - cache->hits+=entry->size; + dbg(lvl_debug,"not in cache"); + return NULL; + } + dbg(lvl_debug,"found 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); + if (entry->where == &cache->t1 || entry->where == &cache->t2) { + cache->hits+=entry->size; #ifdef DEBUG_CACHE - if (entry->where == &cache->t1) - fprintf(stderr,"h"); - else - fprintf(stderr,"H"); + if (entry->where == &cache->t1) + fprintf(stderr,"h"); + else + fprintf(stderr,"H"); #endif - dbg(lvl_debug,"in cache %s", entry->where == &cache->t1 ? "T1" : "T2"); - cache_remove_from_list(entry->where, entry); - cache_insert_mru(NULL, &cache->t2, entry); - entry->usage++; - return &entry->id[cache->id_size]; - } else { - if (entry->where == &cache->b1) { + dbg(lvl_debug,"in cache %s", entry->where == &cache->t1 ? "T1" : "T2"); + cache_remove_from_list(entry->where, entry); + cache_insert_mru(NULL, &cache->t2, entry); + entry->usage++; + return &entry->id[cache->id_size]; + } else { + if (entry->where == &cache->b1) { #ifdef DEBUG_CACHE - fprintf(stderr,"m"); + fprintf(stderr,"m"); #endif - dbg(lvl_debug,"in phantom cache B1"); - cache->t1_target=MIN(cache->t1_target+MAX(cache->b2.size/cache->b1.size, 1),cache->size); - cache_remove_from_list(&cache->b1, entry); - } else if (entry->where == &cache->b2) { + dbg(lvl_debug,"in phantom cache B1"); + cache->t1_target=MIN(cache->t1_target+MAX(cache->b2.size/cache->b1.size, 1),cache->size); + cache_remove_from_list(&cache->b1, entry); + } else if (entry->where == &cache->b2) { #ifdef DEBUG_CACHE - fprintf(stderr,"M"); + fprintf(stderr,"M"); #endif - dbg(lvl_debug,"in phantom cache B2"); - cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0); - cache_remove_from_list(&cache->b2, entry); - } else { - dbg(lvl_error,"**ERROR** invalid where"); - } - cache_replace(cache); - cache_remove(cache, entry); - cache->insert=&cache->t2; - return NULL; - } + dbg(lvl_debug,"in phantom cache B2"); + cache->t1_target=MAX(cache->t1_target-MAX(cache->b1.size/cache->b2.size, 1),0); + cache_remove_from_list(&cache->b2, entry); + } else { + dbg(lvl_error,"**ERROR** invalid where"); + } + cache_replace(cache); + cache_remove(cache, entry); + cache->insert=&cache->t2; + return NULL; + } } void -cache_insert(struct cache *cache, void *data) -{ - struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); - dbg(lvl_debug,"insert 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); - if (cache->insert == &cache->t1) { - if (cache->t1.size + cache->b1.size >= cache->size) { - if (cache->t1.size < cache->size) { - cache_remove_lru(cache, &cache->b1); - cache_replace(cache); - } else { - cache_remove_lru(cache, &cache->t1); - } - } else { - if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) { - if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size) - cache_remove_lru(cache, &cache->b2); - cache_replace(cache); - } - } - } - cache_insert_mru(cache, cache->insert, entry); +cache_insert(struct cache *cache, void *data) { + struct cache_entry *entry=(struct cache_entry *)((char *)data-cache->entry_size); + dbg(lvl_debug,"insert 0x%x 0x%x 0x%x 0x%x 0x%x", entry->id[0], entry->id[1], entry->id[2], entry->id[3], entry->id[4]); + if (cache->insert == &cache->t1) { + if (cache->t1.size + cache->b1.size >= cache->size) { + if (cache->t1.size < cache->size) { + cache_remove_lru(cache, &cache->b1); + cache_replace(cache); + } else { + cache_remove_lru(cache, &cache->t1); + } + } else { + if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= cache->size) { + if (cache->t1.size + cache->t2.size + cache->b1.size + cache->b2.size >= 2*cache->size) + cache_remove_lru(cache, &cache->b2); + cache_replace(cache); + } + } + } + cache_insert_mru(cache, cache->insert, entry); } void * -cache_insert_new(struct cache *cache, void *id, int size) -{ - void *data=cache_entry_new(cache, id, size); - cache_insert(cache, data); - return data; +cache_insert_new(struct cache *cache, void *id, int size) { + void *data=cache_entry_new(cache, id, size); + cache_insert(cache, data); + return data; } static void -cache_stats(struct cache *cache) -{ - dbg(lvl_debug,"hits %d misses %d hitratio %d size %d entry_size %d id_size %d T1 target %d", cache->hits, cache->misses, cache->hits*100/(cache->hits+cache->misses), cache->size, cache->entry_size, cache->id_size, cache->t1_target); - dbg(lvl_debug,"T1:%d B1:%d T2:%d B2:%d", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size); - cache->hits=0; - cache->misses=0; +cache_stats(struct cache *cache) { + dbg(lvl_debug,"hits %d misses %d hitratio %d size %d entry_size %d id_size %d T1 target %d", cache->hits, cache->misses, + cache->hits*100/(cache->hits+cache->misses), cache->size, cache->entry_size, cache->id_size, cache->t1_target); + dbg(lvl_debug,"T1:%d B1:%d T2:%d B2:%d", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size); + cache->hits=0; + cache->misses=0; } void -cache_dump(struct cache *cache) -{ - cache_stats(cache); - cache_list_dump("T1", cache, &cache->t1); - cache_list_dump("B1", cache, &cache->b1); - cache_list_dump("T2", cache, &cache->t2); - cache_list_dump("B2", cache, &cache->b2); - dbg(lvl_debug,"dump end"); +cache_dump(struct cache *cache) { + cache_stats(cache); + cache_list_dump("T1", cache, &cache->t1); + cache_list_dump("B1", cache, &cache->b1); + cache_list_dump("T2", cache, &cache->t2); + cache_list_dump("B2", cache, &cache->b2); + dbg(lvl_debug,"dump end"); } |