Add generic hash map implementation.

Reimplement both font cache and glyph cache on top of it.


git-svn-id: svn://svn.mplayerhq.hu/mplayer/trunk@23034 b3059339-0415-0410-9bf9-f77b7e298cf2

2 files changed, 179 insertions, 120 deletions

diff --git a/libass/ass_cache.c b/libass/ass_cache.c
index 463fdb50af..a11d2fea7a 100644
--- a/libass/ass_cache.c
+++ b/libass/ass_cache.c
@@ -34,12 +34,146 @@
 #include "ass_bitmap.h"
 #include "ass_cache.h"
 
-#define MAX_FONT_CACHE_SIZE 100
 
-static ass_font_t** font_cache;
-static int font_cache_size;
+typedef struct hashmap_item_s {
+	void* key;
+	void* value;
+	struct hashmap_item_s* next;
+} hashmap_item_t;
+typedef hashmap_item_t* hashmap_item_p;
 
-static int font_compare(ass_font_desc_t* a, ass_font_desc_t* b) {
+struct hashmap_s {
+	int nbuckets;
+	size_t key_size, value_size;
+	hashmap_item_p* root;
+	int count;
+	hashmap_item_dtor_t item_dtor; // a destructor for hashmap key/value pairs
+	hashmap_key_compare_t key_compare;
+	hashmap_hash_t hash;
+};
+
+#define FNV1_32A_INIT (unsigned)0x811c9dc5
+
+static inline unsigned fnv_32a_buf(void* buf, size_t len, unsigned hval)
+{
+	unsigned char *bp = buf;
+	unsigned char *be = bp + len;
+	while (bp < be) {
+		hval ^= (unsigned)*bp++;
+		hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
+	}
+	return hval;
+}
+static inline unsigned fnv_32a_str(char* str, unsigned hval)
+{
+	unsigned char* s = (unsigned char*)str;
+	while (*s) {
+		hval ^= (unsigned)*s++;
+		hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
+	}
+	return hval;
+}
+
+static unsigned hashmap_hash(void* buf, size_t len)
+{
+	return fnv_32a_buf(buf, len, FNV1_32A_INIT);
+}
+
+static int hashmap_key_compare(void* a, void* b, size_t size)
+{
+	return (memcmp(a, b, size) == 0);
+}
+
+static void hashmap_item_dtor(void* key, size_t key_size, void* value, size_t value_size)
+{
+	free(key);
+	free(value);
+}
+
+hashmap_t* hashmap_init(size_t key_size, size_t value_size, int nbuckets,
+			hashmap_item_dtor_t item_dtor, hashmap_key_compare_t key_compare,
+			hashmap_hash_t hash)
+{
+	hashmap_t* map = calloc(1, sizeof(hashmap_t));
+	map->nbuckets = nbuckets;
+	map->key_size = key_size;
+	map->value_size = value_size;
+	map->count = 0;
+	map->root = calloc(nbuckets, sizeof(hashmap_item_p));
+	map->item_dtor = item_dtor ? item_dtor : hashmap_item_dtor;
+	map->key_compare = key_compare ? key_compare : hashmap_key_compare;
+	map->hash = hash ? hash : hashmap_hash;
+	return map;
+}
+
+void hashmap_done(hashmap_t* map)
+{
+	int i;
+	for (i = 0; i < map->nbuckets; ++i) {
+		hashmap_item_t* item = map->root[i];
+		while (item) {
+			hashmap_item_t* next = item->next;
+			map->item_dtor(item->key, map->key_size, item->value, map->value_size);
+			free(item);
+			item = next;
+		}
+	}
+	free(map->root);
+	free(map);
+}
+
+// does nothing if key already exists
+void hashmap_insert(hashmap_t* map, void* key, void* value)
+{
+	unsigned hash = map->hash(key, map->key_size);
+	hashmap_item_t** next = map->root + (hash % map->nbuckets);
+	while (*next) {
+		if (map->key_compare(key, (*next)->key, map->key_size))
+			return;
+		next = &((*next)->next);
+		assert(next);
+	}
+	(*next) = malloc(sizeof(hashmap_item_t));
+	(*next)->key = malloc(map->key_size);
+	(*next)->value = malloc(map->value_size);
+	memcpy((*next)->key, key, map->key_size);
+	memcpy((*next)->value, value, map->value_size);
+	(*next)->next = 0;
+
+	map->count ++;
+}
+
+void* hashmap_find(hashmap_t* map, void* key)
+{
+	unsigned hash = map->hash(key, map->key_size);
+	hashmap_item_t* item = map->root[hash % map->nbuckets];
+	while (item) {
+		if (map->key_compare(key, item->key, map->key_size)) {
+			return item->value;
+		}
+		item = item->next;
+	}
+	return 0;
+}
+
+//---------------------------------
+// font cache
+
+hashmap_t* font_cache;
+
+static unsigned font_desc_hash(void* buf, size_t len)
+{
+	ass_font_desc_t* desc = buf;
+	unsigned hval;
+	hval = fnv_32a_str(desc->family, FNV1_32A_INIT);
+	hval = fnv_32a_buf(&desc->bold, sizeof(desc->bold), hval);
+	hval = fnv_32a_buf(&desc->italic, sizeof(desc->italic), hval);
+	return hval;
+}
+
+static int font_compare(void* key1, void* key2, size_t key_size) {
+	ass_font_desc_t* a = key1;
+	ass_font_desc_t* b = key2;
 	if (strcmp(a->family, b->family) != 0)
 		return 0;
 	if (a->bold != b->bold)
@@ -49,20 +183,15 @@ static int font_compare(ass_font_desc_t* a, ass_font_desc_t* b) {
 	return 1;
 }
 
-/**
- * \brief Get a face struct from cache.
- * \param desc required face description
- * \return font struct
-*/
-ass_font_t* ass_font_cache_find(ass_font_desc_t* desc)
+static void font_hash_dtor(void* key, size_t key_size, void* value, size_t value_size)
 {
-	int i;
-	
-	for (i=0; i<font_cache_size; ++i)
-		if (font_compare(desc, &(font_cache[i]->desc)))
-			return font_cache[i];
+	ass_font_free(value);
+	free(key);
+}
 
-	return 0;
+ass_font_t* ass_font_cache_find(ass_font_desc_t* desc)
+{
+	return hashmap_find(font_cache, desc);
 }
 
 /**
@@ -71,103 +200,40 @@ ass_font_t* ass_font_cache_find(ass_font_desc_t* desc)
 */
 void ass_font_cache_add(ass_font_t* font)
 {
-	if (font_cache_size == MAX_FONT_CACHE_SIZE) {
-		mp_msg(MSGT_ASS, MSGL_FATAL, MSGTR_LIBASS_TooManyFonts);
-		// FIXME: possible memory leak
-		return;
-	}
-
-	font_cache[font_cache_size] = font;
-	font_cache_size++;
+	hashmap_insert(font_cache, &(font->desc), font);
 }
 
 void ass_font_cache_init(void)
 {
-	font_cache = calloc(MAX_FONT_CACHE_SIZE, sizeof(ass_font_t*));
-	font_cache_size = 0;
+	font_cache = hashmap_init(sizeof(ass_font_desc_t),
+				  sizeof(ass_font_t),
+				  1000,
+				  font_hash_dtor, font_compare, font_desc_hash);
 }
 
 void ass_font_cache_done(void)
 {
-	int i;
-	for (i = 0; i < font_cache_size; ++i) {
-		ass_font_t* item = font_cache[i];
-		ass_font_free(item);
-	}
-	free(font_cache);
-	font_cache_size = 0;
+	hashmap_done(font_cache);
 }
 
 //---------------------------------
 // glyph cache
 
-#define GLYPH_HASH_SIZE (0xFFFF + 13)
-
-typedef struct glyph_hash_item_s {
-	glyph_hash_key_t key;
-	glyph_hash_val_t val;
-	struct glyph_hash_item_s* next;
-} glyph_hash_item_t;
-
-typedef glyph_hash_item_t* glyph_hash_item_p;
+hashmap_t* glyph_cache;
 
-static glyph_hash_item_p* glyph_hash_root;
-static int glyph_hash_size;
-
-static int glyph_compare(glyph_hash_key_t* a, glyph_hash_key_t* b) {
-	if (memcmp(a, b, sizeof(glyph_hash_key_t)) == 0)
-		return 1;
-	else
-		return 0;
-}
-
-static unsigned glyph_hash(glyph_hash_key_t* key) {
-	unsigned val = 0;
-	unsigned i;
-	for (i = 0; i < sizeof(key->font); ++i)
-		val += *(unsigned char *)(&(key->font) + i);
-	val <<= 21;
-	
-	if (key->bitmap)   val &= 0x80000000;
-	if (key->be) val &= 0x40000000;
-	val += key->ch;
-	val += key->size << 8;
-	val += key->outline << 3;
-	val += key->advance.x << 10;
-	val += key->advance.y << 16;
-	val += key->bold << 1;
-	val += key->italic << 20;
-	val += key->frx;
-	val += key->fry << 1;
-	val += key->frz << 2;
-	return val;
+static void glyph_hash_dtor(void* key, size_t key_size, void* value, size_t value_size)
+{
+	glyph_hash_val_t* v = value;
+	if (v->bm) ass_free_bitmap(v->bm);
+	if (v->bm_o) ass_free_bitmap(v->bm_o);
+	if (v->bm_s) ass_free_bitmap(v->bm_s);
+	free(key);
+	free(value);
 }
 
-/**
- * \brief Add a glyph to glyph cache.
- * \param key hash key
- * \param val hash val: 2 bitmap glyphs + some additional info
-*/ 
 void cache_add_glyph(glyph_hash_key_t* key, glyph_hash_val_t* val)
 {
-	unsigned hash = glyph_hash(key);
-	glyph_hash_item_t** next = glyph_hash_root + (hash % GLYPH_HASH_SIZE);
-	while (*next) {
-		if (glyph_compare(key, &((*next)->key)))
-			return;
-		next = &((*next)->next);
-		assert(next);
-	}
-	(*next) = malloc(sizeof(glyph_hash_item_t));
-//	(*next)->desc = glyph_key_copy(key, &((*next)->key));
-	memcpy(&((*next)->key), key, sizeof(glyph_hash_key_t));
-	memcpy(&((*next)->val), val, sizeof(glyph_hash_val_t));
-	(*next)->next = 0;
-
-	glyph_hash_size ++;
-/*	if (glyph_hash_size  && (glyph_hash_size % 25 == 0)) {
-		printf("\nGlyph cache: %d entries, %d bytes\n", glyph_hash_size, glyph_hash_size * sizeof(glyph_hash_item_t));
-	} */
+	hashmap_insert(glyph_cache, key, val);
 }
 
 /**
@@ -177,39 +243,20 @@ void cache_add_glyph(glyph_hash_key_t* key, glyph_hash_val_t* val)
 */ 
 glyph_hash_val_t* cache_find_glyph(glyph_hash_key_t* key)
 {
-	unsigned hash = glyph_hash(key);
-	glyph_hash_item_t* item = glyph_hash_root[hash % GLYPH_HASH_SIZE];
-	while (item) {
-		if (glyph_compare(key, &(item->key))) {
-			return &(item->val);
-		}
-		item = item->next;
-	}
-	return 0;
+	return hashmap_find(glyph_cache, key);
 }
 
 void ass_glyph_cache_init(void)
 {
-	glyph_hash_root = calloc(GLYPH_HASH_SIZE, sizeof(glyph_hash_item_p));
-	glyph_hash_size = 0;
+	glyph_cache = hashmap_init(sizeof(glyph_hash_key_t),
+				   sizeof(glyph_hash_val_t),
+				   0xFFFF + 13,
+				   glyph_hash_dtor, NULL, NULL);
 }
 
 void ass_glyph_cache_done(void)
 {
-	int i;
-	for (i = 0; i < GLYPH_HASH_SIZE; ++i) {
-		glyph_hash_item_t* item = glyph_hash_root[i];
-		while (item) {
-			glyph_hash_item_t* next = item->next;
-			if (item->val.bm) ass_free_bitmap(item->val.bm);
-			if (item->val.bm_o) ass_free_bitmap(item->val.bm_o);
-			if (item->val.bm_s) ass_free_bitmap(item->val.bm_s);
-			free(item);
-			item = next;
-		}
-	}
-	free(glyph_hash_root);
-	glyph_hash_size = 0;
+	hashmap_done(glyph_cache);
 }
 
 void ass_glyph_cache_reset(void)
diff --git a/libass/ass_cache.h b/libass/ass_cache.h
index a4a5bf4ce1..8e074579db 100644
--- a/libass/ass_cache.h
+++ b/libass/ass_cache.h
@@ -58,5 +58,17 @@ glyph_hash_val_t* cache_find_glyph(glyph_hash_key_t* key);
 void ass_glyph_cache_reset(void);
 void ass_glyph_cache_done(void);
 
+typedef struct hashmap_s hashmap_t;
+typedef void (*hashmap_item_dtor_t)(void* key, size_t key_size, void* value, size_t value_size);
+typedef int (*hashmap_key_compare_t)(void* key1, void* key2, size_t key_size);
+typedef unsigned (*hashmap_hash_t)(void* key, size_t key_size);
+
+hashmap_t* hashmap_init(size_t key_size, size_t value_size, int nbuckets,
+			hashmap_item_dtor_t item_dtor, hashmap_key_compare_t key_compare,
+			hashmap_hash_t hash);
+void hashmap_done(hashmap_t* map);
+void hashmap_insert(hashmap_t* map, void* key, void* value);
+void* hashmap_find(hashmap_t* map, void* key);
+
 #endif