[MPlayer-cvslog] r23034 - in trunk/libass: ass_cache.c ass_cache.h
eugeni
subversion at mplayerhq.hu
Sat Apr 21 01:00:30 CEST 2007
Author: eugeni
Date: Sat Apr 21 01:00:30 2007
New Revision: 23034
Modified:
trunk/libass/ass_cache.c
trunk/libass/ass_cache.h
Log:
Add generic hash map implementation.
Reimplement both font cache and glyph cache on top of it.
Modified: trunk/libass/ass_cache.c
==============================================================================
--- trunk/libass/ass_cache.c (original)
+++ trunk/libass/ass_cache.c Sat Apr 21 01:00:30 2007
@@ -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*
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
*/
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;
-
-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;
-}
+hashmap_t* glyph_cache;
-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* k
*/
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)
Modified: trunk/libass/ass_cache.h
==============================================================================
--- trunk/libass/ass_cache.h (original)
+++ trunk/libass/ass_cache.h Sat Apr 21 01:00:30 2007
@@ -58,5 +58,17 @@ glyph_hash_val_t* cache_find_glyph(glyph
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
More information about the MPlayer-cvslog
mailing list