From 4408714100860452be4ecf9e7e6b8cc7527955d9 Mon Sep 17 00:00:00 2001 From: eugeni Date: Fri, 20 Apr 2007 23:00:30 +0000 Subject: 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 --- libass/ass_cache.c | 287 +++++++++++++++++++++++++++++++---------------------- libass/ass_cache.h | 12 +++ 2 files changed, 179 insertions(+), 120 deletions(-) (limited to 'libass') 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; idesc))) - 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 -- cgit v1.2.3