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.

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;