diff options
Diffstat (limited to 'fitz/base_hash.c')
| -rw-r--r-- | fitz/base_hash.c | 111 |
1 files changed, 74 insertions, 37 deletions
diff --git a/fitz/base_hash.c b/fitz/base_hash.c index 630f6b6a..4ba02f4d 100644 --- a/fitz/base_hash.c +++ b/fitz/base_hash.c @@ -1,4 +1,4 @@ -#include "fitz.h" +#include "fitz-internal.h" /* Simple hashtable with open addressing linear probe. @@ -22,6 +22,7 @@ struct fz_hash_table_s int keylen; int size; int load; + int lock; /* -1 or the lock used to protect this hash table */ fz_hash_entry *ents; }; @@ -42,7 +43,7 @@ static unsigned hash(unsigned char *s, int len) } fz_hash_table * -fz_new_hash_table(fz_context *ctx, int initialsize, int keylen) +fz_new_hash_table(fz_context *ctx, int initialsize, int keylen, int lock) { fz_hash_table *table; @@ -52,6 +53,7 @@ fz_new_hash_table(fz_context *ctx, int initialsize, int keylen) table->keylen = keylen; table->size = initialsize; table->load = 0; + table->lock = lock; fz_try(ctx) { table->ents = fz_malloc_array(ctx, table->size, sizeof(fz_hash_entry)); @@ -98,10 +100,45 @@ fz_free_hash(fz_context *ctx, fz_hash_table *table) fz_free(ctx, table); } +static void * +do_hash_insert(fz_context *ctx, fz_hash_table *table, void *key, void *val) +{ + fz_hash_entry *ents; + unsigned size; + unsigned pos; + + ents = table->ents; + size = table->size; + pos = hash(key, table->keylen) % size; + + if (table->lock >= 0) + fz_assert_lock_held(ctx, table->lock); + + while (1) + { + if (!ents[pos].val) + { + memcpy(ents[pos].key, key, table->keylen); + ents[pos].val = val; + table->load ++; + return NULL; + } + + if (memcmp(key, ents[pos].key, table->keylen) == 0) + { + fz_warn(ctx, "assert: overwrite hash slot"); + return ents[pos].val; + } + + pos = (pos + 1) % size; + } +} + static void fz_resize_hash(fz_context *ctx, fz_hash_table *table, int newsize) { fz_hash_entry *oldents = table->ents; + fz_hash_entry *newents = table->ents; int oldsize = table->size; int oldload = table->load; int i; @@ -112,7 +149,22 @@ fz_resize_hash(fz_context *ctx, fz_hash_table *table, int newsize) return; } - table->ents = fz_malloc_array(ctx, newsize, sizeof(fz_hash_entry)); + if (table->lock == FZ_LOCK_ALLOC) + fz_unlock(ctx, FZ_LOCK_ALLOC); + newents = fz_malloc_array(ctx, newsize, sizeof(fz_hash_entry)); + if (table->lock == FZ_LOCK_ALLOC) + fz_lock(ctx, FZ_LOCK_ALLOC); + if (table->lock >= 0) + { + if (table->size >= newsize) + { + /* Someone else fixed it before we could lock! */ + fz_unlock(ctx, table->lock); + fz_free(ctx, newents); + return; + } + } + table->ents = newents; memset(table->ents, 0, sizeof(fz_hash_entry) * newsize); table->size = newsize; table->load = 0; @@ -121,11 +173,15 @@ fz_resize_hash(fz_context *ctx, fz_hash_table *table, int newsize) { if (oldents[i].val) { - fz_hash_insert(ctx, table, oldents[i].key, oldents[i].val); + do_hash_insert(ctx, table, oldents[i].key, oldents[i].val); } } + if (table->lock == FZ_LOCK_ALLOC) + fz_unlock(ctx, FZ_LOCK_ALLOC); fz_free(ctx, oldents); + if (table->lock == FZ_LOCK_ALLOC) + fz_lock(ctx, FZ_LOCK_ALLOC); } void * @@ -135,6 +191,9 @@ fz_hash_find(fz_context *ctx, fz_hash_table *table, void *key) unsigned size = table->size; unsigned pos = hash(key, table->keylen) % size; + if (table->lock >= 0) + fz_assert_lock_held(ctx, table->lock); + while (1) { if (!ents[pos].val) @@ -150,37 +209,12 @@ fz_hash_find(fz_context *ctx, fz_hash_table *table, void *key) void * fz_hash_insert(fz_context *ctx, fz_hash_table *table, void *key, void *val) { - fz_hash_entry *ents; - unsigned size; - unsigned pos; - if (table->load > table->size * 8 / 10) { fz_resize_hash(ctx, table, table->size * 2); } - ents = table->ents; - size = table->size; - pos = hash(key, table->keylen) % size; - - while (1) - { - if (!ents[pos].val) - { - memcpy(ents[pos].key, key, table->keylen); - ents[pos].val = val; - table->load ++; - return NULL; - } - - if (memcmp(key, ents[pos].key, table->keylen) == 0) - { - fz_warn(ctx, "assert: overwrite hash slot"); - return ents[pos].val; - } - - pos = (pos + 1) % size; - } + return do_hash_insert(ctx, table, key, val); } void @@ -191,11 +225,14 @@ fz_hash_remove(fz_context *ctx, fz_hash_table *table, void *key) unsigned pos = hash(key, table->keylen) % size; unsigned hole, look, code; + if (table->lock >= 0) + fz_assert_lock_held(ctx, table->lock); + while (1) { if (!ents[pos].val) { - fz_warn(ctx, "assert: remove inexistent hash entry"); + fz_warn(ctx, "assert: remove non-existent hash entry"); return; } @@ -231,22 +268,22 @@ fz_hash_remove(fz_context *ctx, fz_hash_table *table, void *key) } void -fz_debug_hash(fz_context *ctx, fz_hash_table *table) +fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table) { int i, k; - printf("cache load %d / %d\n", table->load, table->size); + fprintf(out, "cache load %d / %d\n", table->load, table->size); for (i = 0; i < table->size; i++) { if (!table->ents[i].val) - printf("table % 4d: empty\n", i); + fprintf(out, "table % 4d: empty\n", i); else { - printf("table % 4d: key=", i); + fprintf(out, "table % 4d: key=", i); for (k = 0; k < MAX_KEY_LEN; k++) - printf("%02x", ((char*)table->ents[i].key)[k]); - printf(" val=$%p\n", table->ents[i].val); + fprintf(out, "%02x", ((char*)table->ents[i].key)[k]); + fprintf(out, " val=$%p\n", table->ents[i].val); } } } |