From 2af7318239c59555869d018bc355fe0e21d900c6 Mon Sep 17 00:00:00 2001 From: Nikias Bassen Date: Thu, 12 May 2016 02:32:55 +0200 Subject: bplist: Speed up plist_to_bin conversion for large plists Using a better hashing algorithm and a larger hash table the conversion is A LOT faster when processing large plists. Thanks to Xiao Deng for reporting this issue and suggesting a fix. --- src/bplist.c | 11 +++++++---- src/hashtable.c | 8 ++++---- src/hashtable.h | 2 +- 3 files changed, 12 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/bplist.c b/src/bplist.c index 3ba46a2..bb73b31 100644 --- a/src/bplist.c +++ b/src/bplist.c @@ -735,7 +735,7 @@ static unsigned int plist_data_hash(const void* key) case PLIST_KEY: case PLIST_STRING: buff = data->strval; - size = strlen(buff); + size = data->length; break; case PLIST_DATA: case PLIST_ARRAY: @@ -752,9 +752,12 @@ static unsigned int plist_data_hash(const void* key) break; } - //now perform hash - for (i = 0; i < size; buff++, i++) - hash = hash << 7 ^ (*buff); + // now perform hash using djb2 hashing algorithm + // see: http://www.cse.yorku.ca/~oz/hash.html + hash += 5381; + for (i = 0; i < size; buff++, i++) { + hash = ((hash << 5) + hash) + *buff; + } return hash; } diff --git a/src/hashtable.c b/src/hashtable.c index 08ff934..3568f3c 100644 --- a/src/hashtable.c +++ b/src/hashtable.c @@ -24,7 +24,7 @@ hashtable_t* hash_table_new(hash_func_t hash_func, compare_func_t compare_func) { hashtable_t* ht = (hashtable_t*)malloc(sizeof(hashtable_t)); int i; - for (i = 0; i < 256; i++) { + for (i = 0; i < 4096; i++) { ht->entries[i] = NULL; } ht->count = 0; @@ -38,7 +38,7 @@ void hash_table_destroy(hashtable_t *ht) if (!ht) return; int i = 0; - for (i = 0; i < 256; i++) { + for (i = 0; i < 4096; i++) { if (ht->entries[i]) { hashentry_t* e = ht->entries[i]; while (e) { @@ -58,7 +58,7 @@ void hash_table_insert(hashtable_t* ht, void *key, void *value) unsigned int hash = ht->hash_func(key); - int idx0 = hash & 0xFF; + int idx0 = hash & 0xFFF; // get the idx0 list hashentry_t* e = ht->entries[idx0]; @@ -93,7 +93,7 @@ void* hash_table_lookup(hashtable_t* ht, void *key) if (!ht || !key) return NULL; unsigned int hash = ht->hash_func(key); - int idx0 = hash & 0xFF; + int idx0 = hash & 0xFFF; hashentry_t* e = ht->entries[idx0]; while (e) { diff --git a/src/hashtable.h b/src/hashtable.h index c28de91..60a40ab 100644 --- a/src/hashtable.h +++ b/src/hashtable.h @@ -32,7 +32,7 @@ typedef unsigned int(*hash_func_t)(const void* key); typedef int (*compare_func_t)(const void *a, const void *b); typedef struct hashtable_t { - hashentry_t *entries[256]; + hashentry_t *entries[4096]; size_t count; hash_func_t hash_func; compare_func_t compare_func; -- cgit v1.1-32-gdbae