diff options
| author |  Nikias Bassen | 2016-05-12 02:32:55 +0200 |
|---|---|---|
| committer | Nikias Bassen | 2016-05-12 02:32:55 +0200 |
| commit | 2af7318239c59555869d018bc355fe0e21d900c6 (patch) | |
| tree | 3b366f10c04d305c9bd72e31e28ca62596ba07dd | |
| parent | 6ab7e301f1854fd18891ddfeaa64e7485be990ba (diff) | |
| download | libplist-2af7318239c59555869d018bc355fe0e21d900c6.tar.gz libplist-2af7318239c59555869d018bc355fe0e21d900c6.tar.bz2 | |
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.
| -rw-r--r-- | src/bplist.c | 11 | ||||
| -rw-r--r-- | src/hashtable.c | 8 | ||||
| -rw-r--r-- | src/hashtable.h | 2 |
3 files changed, 12 insertions, 9 deletions
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; |