From 06e2985ab63838d07b4f2a4d02a87069ec4fa017 Mon Sep 17 00:00:00 2001 From: martin-s Date: Sun, 12 Oct 2008 20:39:00 +0000 Subject: [PATCH] Add:Core:First try to add a general purpose cache to navit git-svn-id: https://navit.svn.sourceforge.net/svnroot/navit/trunk@1453 ffa7fe5e-494d-0410-b361-a75ebd5db220 --- navit/navit/Makefile.am | 4 +- navit/navit/cache.c | 368 ++++++++++++++++++++++++++++++++++++++++++++++++ navit/navit/cache.h | 12 ++ navit/navit/file.c | 45 +++++- navit/navit/file.h | 1 + navit/navit/start.c | 1 + 6 files changed, 423 insertions(+), 8 deletions(-) create mode 100644 navit/navit/cache.c create mode 100644 navit/navit/cache.h diff --git a/navit/navit/Makefile.am b/navit/navit/Makefile.am index 8284ef1..ddd036a 100644 --- a/navit/navit/Makefile.am +++ b/navit/navit/Makefile.am @@ -14,11 +14,11 @@ pkgdata_DATA = navit.xml EXTRA_DIST = navit.xml noinst_LTLIBRARIES = libnavit.la -libnavit_la_SOURCES = attr.c callback.c compass.c coord.c country.c cursor.c data_window.c debug.c \ +libnavit_la_SOURCES = attr.c cache.c callback.c compass.c coord.c country.c cursor.c data_window.c debug.c \ event.c event_glib.c event_glib.h file.c graphics.c gui.c item.c layout.c log.c main.c map.c \ mapset.c maptype.c menu.c navit.c navigation.c osd.c param.c phrase.c plugin.c popup.c \ profile.c projection.c route.c search.c speech.c transform.c track.c \ - util.c vehicle.c xmlconfig.c attr.h attr_def.h callback.h color.h compass.h coord.h country.h \ + util.c vehicle.c xmlconfig.c attr.h attr_def.h cache.h callback.h color.h compass.h coord.h country.h \ cursor.h data.h data_window.h data_window_int.h debug.h destination.h draw_info.h endianess.h event.h \ file.h graphics.h gtkext.h gui.h item.h item_def.h keys.h log.h layer.h layout.h main.h map-share.h map.h\ map_data.h mapset.h maptype.h menu.h navigation.h navit.h osd.h \ diff --git a/navit/navit/cache.c b/navit/navit/cache.c new file mode 100644 index 0000000..446cb99 --- /dev/null +++ b/navit/navit/cache.c @@ -0,0 +1,368 @@ +#include +#ifdef DEBUG_CACHE +#include +#endif +#include +#include "debug.h" +#include "cache.h" + +struct cache_entry { + int usage; + 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 { + struct cache_entry_list t1,b1,t2,b2,*insert; + int size,id_size,entry_size; + int t1_target; + int misses; + int hits; + GHashTable *hash; +}; + +static void +cache_entry_dump(struct cache *cache, struct cache_entry *entry) +{ + int i,size; + dbg(0,"Usage: %d size %d\n",entry->usage, entry->size); + if (cache) + size=cache->id_size; + else + size=5; + for (i = 0 ; i < size ; i++) { + dbg(0,"0x%x\n", 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(0,"dump %s %d\n",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]; +} + +static guint +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; + + 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]); +} + +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(0,"cache with id_size of %d not supported\n", id_size); + g_free(cache); + cache=NULL; + } + return cache; +} + +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); +} + +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; +} + +static void +cache_remove(struct cache *cache, struct cache_entry *entry) +{ + 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]); + g_hash_table_remove(cache->hash, (gpointer)(entry->id)); + g_free(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; +} + +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(1,"removing %d\n", 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) +{ + size+=cache->entry_size; + cache->misses+=size; + struct cache_entry *ret=(struct cache_entry *)g_malloc0(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(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]); + entry->usage--; +} + +static struct cache_entry * +cache_trim(struct cache *cache, struct cache_entry *entry) +{ + 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]); + return g_realloc(entry, cache->entry_size); +} + +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; +} + +static int +cache_replace(struct cache *cache) +{ + if (cache->t1.size >= MAX(1,cache->t1_target)) { + dbg(1,"replace 12\n"); + if (!cache_move(cache, &cache->t1, &cache->b1)) + cache_move(cache, &cache->t2, &cache->b2); + } else { + dbg(1,"replace t2\n"); + if (!cache_move(cache, &cache->t2, &cache->b2)) + cache_move(cache, &cache->t1, &cache->b1); + } +#if 0 + if (! entry) { + cache_dump(cache); + exit(0); + } +#endif + return 1; +} + + +void * +cache_lookup(struct cache *cache, void *id) { + struct cache_entry *entry; + + dbg(1,"get %d\n", ((int *)id)[0]); + entry=g_hash_table_lookup(cache->hash, id); + if (entry == NULL) { + cache->insert=&cache->t1; +#ifdef DEBUG_CACHE + fprintf(stderr,"-"); +#endif + dbg(1,"not in cache\n"); + return NULL; + } + 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]); + 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"); +#endif + dbg(1,"in cache %s\n", 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"); +#endif + dbg(1,"in phantom cache B1\n"); + 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"); +#endif + dbg(1,"in phantom cache B2\n"); + 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(0,"**ERROR** invalid where\n"); + } + 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(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]); + 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; +} + +void * +cache_lookup_or_insert(struct cache *cache, void *id, int size) +{ + void *data=cache_lookup(cache, id); + if (! data) { + data=cache_insert_new(cache, id, size); + } + return data; +} + +void +cache_stats(struct cache *cache) +{ + 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); + dbg(0,"T1:%d B1:%d T2:%d B2:%d\n", cache->t1.size, cache->b1.size, cache->t2.size, cache->b2.size); + cache->hits=0; + cache->misses=0; +} + +void +cache_dump(struct cache *cache) +{ + struct cache_entry *first; + first=cache->t1.first; + 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(0,"dump end\n"); +} + diff --git a/navit/navit/cache.h b/navit/navit/cache.h new file mode 100644 index 0000000..923e417 --- /dev/null +++ b/navit/navit/cache.h @@ -0,0 +1,12 @@ +struct cache_entry; +struct cache; +/* prototypes */ +struct cache *cache_new(int id_size, int size); +void *cache_entry_new(struct cache *cache, void *id, int size); +void cache_entry_destroy(struct cache *cache, void *data); +void *cache_lookup(struct cache *cache, void *id); +void cache_insert(struct cache *cache, void *data); +void *cache_insert_new(struct cache *cache, void *id, int size); +void *cache_lookup_or_insert(struct cache *cache, void *id, int size); +void cache_dump(struct cache *cache); +/* end of prototypes */ diff --git a/navit/navit/file.c b/navit/navit/file.c index e8a88b8..4289ba6 100644 --- a/navit/navit/file.c +++ b/navit/navit/file.c @@ -31,6 +31,7 @@ #include #include #include "debug.h" +#include "cache.h" #include "file.h" #include "config.h" @@ -44,6 +45,17 @@ static struct file *file_list; +static GHashTable *file_name_hash; +static int file_name_id; +static struct cache *file_cache; + +struct file_cache_id { + long long offset; + int size; + int file_name_id; + int method; +}; + struct file * file_create(char *name) { @@ -80,7 +92,7 @@ int file_mkdir(char *name, int pflag) { char buffer[strlen(name)+1]; int ret; - char *curr, *next; + char *next; dbg(1,"enter %s %d\n",name,pflag); if (!pflag) { if (file_is_dir(name)) @@ -89,7 +101,7 @@ int file_mkdir(char *name, int pflag) } strcpy(buffer, name); next=buffer; - while (next=strchr(next, '/')) { + while ((next=strchr(next, '/'))) { *next='\0'; if (*buffer) { ret=file_mkdir(buffer, 0); @@ -128,10 +140,14 @@ file_data_read(struct file *file, long long offset, int size) void *ret; if (file->begin) return file->begin+offset; - ret=g_malloc(size); + if (file_cache) { + struct file_cache_id id={offset,size,file->name_id,0}; + ret=cache_lookup_or_insert(file_cache,&id,size); + } else + ret=g_malloc(size); lseek(file->fd, offset, SEEK_SET); if (read(file->fd, ret, size) != size) { - g_free(ret); + file_data_free(file, ret); ret=NULL; } return ret; @@ -175,7 +191,11 @@ file_data_read_compressed(struct file *file, long long offset, int size, int siz char buffer[size]; uLongf destLen=size_uncomp; - ret=g_malloc(size_uncomp); + if (file_cache) { + struct file_cache_id id={offset,size,file->name_id,1}; + ret=cache_lookup_or_insert(file_cache,&id,size_uncomp); + } else + ret=g_malloc(size_uncomp); lseek(file->fd, offset, SEEK_SET); if (read(file->fd, buffer, size) != size) { g_free(ret); @@ -195,7 +215,10 @@ file_data_free(struct file *file, unsigned char *data) { if (file->begin && data >= file->begin && data < file->end) return; - g_free(data); + if (file_cache) { + cache_entry_destroy(file_cache, data); + } else + g_free(data); } int @@ -375,3 +398,13 @@ file_get_param(struct file *file, struct param_list *param, int count) param_add_hex("Size", file->size, ¶m, &count); return i-count; } + +void +file_init(void) +{ +#if 0 + file_name_hash=g_hash_table_new(g_str_hash, g_str_equal); + file_cache=cache_new(sizeof(struct file_cache_id), 2*1024*1024); +#endif +} + diff --git a/navit/navit/file.h b/navit/navit/file.h index 8dae4b0..971e32d 100644 --- a/navit/navit/file.h +++ b/navit/navit/file.h @@ -27,6 +27,7 @@ struct file { unsigned char *end; long long size; char *name; + int name_id; int fd; #if defined(_WIN32) || defined(__CEGCC__) long map_handle; diff --git a/navit/navit/start.c b/navit/navit/start.c index 2e7c73c..249efd0 100644 --- a/navit/navit/start.c +++ b/navit/navit/start.c @@ -77,6 +77,7 @@ int main(int argc, char **argv) main_init(argv[0]); main_init_nls(); debug_init(argv[0]); + file_init(); #ifndef USE_PLUGINS extern void builtin_init(void); builtin_init(); -- 2.7.4