Add:Core:First try to add a general purpose cache to navit

git-svn-id: http://svn.code.sf.net/p/navit/code/trunk/navit@1453 ffa7fe5e-494d-0410-b361-a75ebd5db220

6 files changed, 423 insertions, 8 deletions

diff --git a/navit/Makefile.am b/navit/Makefile.am
index 8284ef14f..ddd036a72 100644
--- a/navit/Makefile.am
+++ b/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/cache.c b/navit/cache.c
new file mode 100644
index 000000000..446cb9900
--- /dev/null
+++ b/navit/cache.c
@@ -0,0 +1,368 @@
+#include <glib.h>
+#ifdef DEBUG_CACHE
+#include <stdio.h>
+#endif
+#include <string.h>
+#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/cache.h b/navit/cache.h
new file mode 100644
index 000000000..923e417f1
--- /dev/null
+++ b/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/file.c b/navit/file.c
index e8a88b81d..4289ba6fb 100644
--- a/navit/file.c
+++ b/navit/file.c
@@ -31,6 +31,7 @@
 #include <glib.h>
 #include <zlib.h>
 #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, &param, &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/file.h b/navit/file.h
index 8dae4b061..971e32d9c 100644
--- a/navit/file.h
+++ b/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/start.c b/navit/start.c
index 2e7c73cbd..249efd06d 100644
--- a/navit/start.c
+++ b/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();