1 files changed, 241 insertions, 98 deletions
diff --git a/src/Common/libzip/zip_hash.c b/src/Common/libzip/zip_hash.c
index 23f9708d..0d9e9961 100644
--- a/src/Common/libzip/zip_hash.c
+++ b/src/Common/libzip/zip_hash.c
@@ -1,6 +1,6 @@
 /*
   zip_hash.c -- hash table string -> uint64
-  Copyright (C) 2015-2016 Dieter Baron and Thomas Klausner
+  Copyright (C) 2015-2017 Dieter Baron and Thomas Klausner
 
   This file is part of libzip, a library to manipulate ZIP archives.
   The authors can be contacted at <libzip@nih.at>
@@ -17,7 +17,7 @@
   3. The names of the authors may not be used to endorse or promote
      products derived from this software without specific prior
      written permission.
- 
+
   THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS
   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
@@ -31,98 +31,179 @@
   IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
+#include "zipint.h"
 #include <stdlib.h>
 #include <string.h>
-#include "zipint.h"
+
+/* parameter for the string hash function */
+#define HASH_MULTIPLIER 33
+#define HASH_START 5381
+
+/* hash table's fill ratio is kept between these by doubling/halfing its size as necessary */
+#define HASH_MAX_FILL .75
+#define HASH_MIN_FILL .01
+
+/* but hash table size is kept between these */
+#define HASH_MIN_SIZE 256
+#define HASH_MAX_SIZE 0x80000000ul
 
 struct zip_hash_entry {
     const zip_uint8_t *name;
     zip_int64_t orig_index;
     zip_int64_t current_index;
     struct zip_hash_entry *next;
+    zip_uint32_t hash_value;
 };
 typedef struct zip_hash_entry zip_hash_entry_t;
 
 struct zip_hash {
-    zip_uint16_t table_size;
+    zip_uint32_t table_size;
+    zip_uint64_t nentries;
     zip_hash_entry_t **table;
 };
 
-zip_hash_t *
-_zip_hash_new(zip_uint16_t table_size, zip_error_t *error)
-{
-    zip_hash_t *hash;
 
-    if (table_size == 0) {
-	zip_error_set(error, ZIP_ER_INTERNAL, 0);
-	return NULL;
+/* free list of entries */
+static void
+free_list(zip_hash_entry_t *entry) {
+    while (entry != NULL) {
+	zip_hash_entry_t *next = entry->next;
+	free(entry);
+	entry = next;
     }
+}
+
+
+/* compute hash of string, full 32 bit value */
+static zip_uint32_t
+hash_string(const zip_uint8_t *name) {
+    zip_uint64_t value = HASH_START;
 
-    if ((hash=(zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) {
+    if (name == NULL) {
+	return 0;
+    }
+
+    while (*name != 0) {
+	value = (zip_uint64_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % 0x100000000ul);
+	name++;
+    }
+
+    return (zip_uint32_t)value;
+}
+
+
+/* resize hash table; new_size must be a power of 2, can be larger or smaller than current size */
+static bool
+hash_resize(zip_hash_t *hash, zip_uint32_t new_size, zip_error_t *error) {
+    zip_hash_entry_t **new_table;
+
+    if (new_size == hash->table_size) {
+	return true;
+    }
+
+    if ((new_table = (zip_hash_entry_t **)calloc(new_size, sizeof(zip_hash_entry_t *))) == NULL) {
 	zip_error_set(error, ZIP_ER_MEMORY, 0);
-	return NULL;
+	return false;
     }
-    hash->table_size = table_size;
-    if ((hash->table=(zip_hash_entry_t**)calloc(table_size, sizeof(zip_hash_entry_t *))) == NULL) {
-	free(hash);
+
+    if (hash->nentries > 0) {
+	zip_uint32_t i;
+
+	for (i = 0; i < hash->table_size; i++) {
+	    zip_hash_entry_t *entry = hash->table[i];
+	    while (entry) {
+		zip_hash_entry_t *next = entry->next;
+
+		zip_uint32_t new_index = entry->hash_value % new_size;
+
+		entry->next = new_table[new_index];
+		new_table[new_index] = entry;
+
+		entry = next;
+	    }
+	}
+    }
+
+    free(hash->table);
+    hash->table = new_table;
+    hash->table_size = new_size;
+
+    return true;
+}
+
+
+static zip_uint32_t
+size_for_capacity(zip_uint64_t capacity) {
+    double needed_size = capacity / HASH_MAX_FILL;
+    zip_uint32_t v;
+
+    if (needed_size > ZIP_UINT32_MAX) {
+	v = ZIP_UINT32_MAX;
+    }
+    else {
+	v = (zip_uint32_t)needed_size;
+    }
+
+    if (v > HASH_MAX_SIZE) {
+	return HASH_MAX_SIZE;
+    }
+
+    /* From Bit Twiddling Hacks by Sean Eron Anderson <seander@cs.stanford.edu>
+     (http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2). */
+
+    v--;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    v++;
+
+    return v;
+}
+
+
+zip_hash_t *
+_zip_hash_new(zip_error_t *error) {
+    zip_hash_t *hash;
+
+    if ((hash = (zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) {
 	zip_error_set(error, ZIP_ER_MEMORY, 0);
 	return NULL;
     }
 
+    hash->table_size = 0;
+    hash->nentries = 0;
+    hash->table = NULL;
+
     return hash;
 }
 
-static void
-_free_list(zip_hash_entry_t *entry)
-{
-    zip_hash_entry_t *next;
-    do {
-	next = entry->next;
-	free(entry);
-	entry = next;
-    } while (entry != NULL);
-}
 
 void
-_zip_hash_free(zip_hash_t *hash)
-{
-    zip_uint16_t i;
+_zip_hash_free(zip_hash_t *hash) {
+    zip_uint32_t i;
 
     if (hash == NULL) {
 	return;
     }
 
-    for (i=0; i<hash->table_size; i++) {
-	if (hash->table[i] != NULL) {
-	    _free_list(hash->table[i]);
+    if (hash->table != NULL) {
+	for (i = 0; i < hash->table_size; i++) {
+	    if (hash->table[i] != NULL) {
+		free_list(hash->table[i]);
+	    }
 	}
+	free(hash->table);
     }
-    free(hash->table);
     free(hash);
 }
 
-static zip_uint16_t
-_hash_string(const zip_uint8_t *name, zip_uint16_t size)
-{
-#define HASH_MULTIPLIER 33
-    zip_uint16_t value = 5381;
-
-    if (name == NULL)
-	return 0;
-
-    while (*name != 0) {
-	value = (zip_uint16_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % size);
-	name++;
-    }
-
-    return value;
-}
 
 /* insert into hash, return error on existence or memory issues */
 bool
-_zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip_flags_t flags, zip_error_t *error)
-{
-    zip_uint16_t hash_value;
+_zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip_flags_t flags, zip_error_t *error) {
+    zip_uint32_t hash_value, table_index;
     zip_hash_entry_t *entry;
 
     if (hash == NULL || name == NULL || index > ZIP_INT64_MAX) {
@@ -130,9 +211,17 @@ _zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip
 	return false;
     }
 
-    hash_value = _hash_string(name, hash->table_size);
-    for (entry = hash->table[hash_value]; entry != NULL; entry = entry->next) {
-	if (strcmp((const char *)name, (const char *)entry->name) == 0) {
+    if (hash->table_size == 0) {
+	if (!hash_resize(hash, HASH_MIN_SIZE, error)) {
+	    return false;
+	}
+    }
+
+    hash_value = hash_string(name);
+    table_index = hash_value % hash->table_size;
+
+    for (entry = hash->table[table_index]; entry != NULL; entry = entry->next) {
+	if (entry->hash_value == hash_value && strcmp((const char *)name, (const char *)entry->name) == 0) {
 	    if (((flags & ZIP_FL_UNCHANGED) && entry->orig_index != -1) || entry->current_index != -1) {
 		zip_error_set(error, ZIP_ER_EXISTS, 0);
 		return false;
@@ -144,14 +233,21 @@ _zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip
     }
 
     if (entry == NULL) {
-	if ((entry=(zip_hash_entry_t *)malloc(sizeof(zip_hash_entry_t))) == NULL) {
+	if ((entry = (zip_hash_entry_t *)malloc(sizeof(zip_hash_entry_t))) == NULL) {
 	    zip_error_set(error, ZIP_ER_MEMORY, 0);
 	    return false;
 	}
 	entry->name = name;
-	entry->next = hash->table[hash_value];
-	hash->table[hash_value] = entry;
+	entry->next = hash->table[table_index];
+	hash->table[table_index] = entry;
+	entry->hash_value = hash_value;
 	entry->orig_index = -1;
+	hash->nentries++;
+	if (hash->nentries > hash->table_size * HASH_MAX_FILL && hash->table_size < HASH_MAX_SIZE) {
+	    if (!hash_resize(hash, hash->table_size * 2, error)) {
+		return false;
+	    }
+	}
     }
 
     if (flags & ZIP_FL_UNCHANGED) {
@@ -162,11 +258,11 @@ _zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip
     return true;
 }
 
+
 /* remove entry from hash, error if not found */
 bool
-_zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error)
-{
-    zip_uint16_t hash_value;
+_zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error) {
+    zip_uint32_t hash_value, index;
     zip_hash_entry_t *entry, *previous;
 
     if (hash == NULL || name == NULL) {
@@ -174,38 +270,47 @@ _zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error)
 	return false;
     }
 
-    hash_value = _hash_string(name, hash->table_size);
-    previous = NULL;
-    entry = hash->table[hash_value];
-    while (entry) {
-	if (strcmp((const char *)name, (const char *)entry->name) == 0) {
-	    if (entry->orig_index == -1) {
-		if (previous) {
-		    previous->next = entry->next;
+    if (hash->nentries > 0) {
+	hash_value = hash_string(name);
+	index = hash_value % hash->table_size;
+	previous = NULL;
+	entry = hash->table[index];
+	while (entry) {
+	    if (entry->hash_value == hash_value && strcmp((const char *)name, (const char *)entry->name) == 0) {
+		if (entry->orig_index == -1) {
+		    if (previous) {
+			previous->next = entry->next;
+		    }
+		    else {
+			hash->table[index] = entry->next;
+		    }
+		    free(entry);
+		    hash->nentries--;
+		    if (hash->nentries < hash->table_size * HASH_MIN_FILL && hash->table_size > HASH_MIN_SIZE) {
+			if (!hash_resize(hash, hash->table_size / 2, error)) {
+			    return false;
+			}
+		    }
 		}
 		else {
-		    hash->table[hash_value] = entry->next;
+		    entry->current_index = -1;
 		}
-		free(entry);
+		return true;
 	    }
-	    else {
-		entry->current_index = -1;
-	    }
-	    return true;
+	    previous = entry;
+	    entry = entry->next;
 	}
-	previous = entry;
-	entry = entry->next;
-    };
+    }
 
     zip_error_set(error, ZIP_ER_NOENT, 0);
     return false;
 }
 
+
 /* find value for entry in hash, -1 if not found */
 zip_int64_t
-_zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, zip_error_t *error)
-{
-    zip_uint16_t hash_value;
+_zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, zip_error_t *error) {
+    zip_uint32_t hash_value, index;
     zip_hash_entry_t *entry;
 
     if (hash == NULL || name == NULL) {
@@ -213,33 +318,58 @@ _zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, z
 	return -1;
     }
 
-    hash_value = _hash_string(name, hash->table_size);
-    for (entry = hash->table[hash_value]; entry != NULL; entry = entry->next) {
-	if (strcmp((const char *)name, (const char *)entry->name) == 0) {
-	    if (flags & ZIP_FL_UNCHANGED) {
-		if (entry->orig_index != -1) {
-		    return entry->orig_index;
+    if (hash->nentries > 0) {
+	hash_value = hash_string(name);
+	index = hash_value % hash->table_size;
+	for (entry = hash->table[index]; entry != NULL; entry = entry->next) {
+	    if (strcmp((const char *)name, (const char *)entry->name) == 0) {
+		if (flags & ZIP_FL_UNCHANGED) {
+		    if (entry->orig_index != -1) {
+			return entry->orig_index;
+		    }
 		}
-	    }
-	    else {
-		if (entry->current_index != -1) {
-		    return entry->current_index;
+		else {
+		    if (entry->current_index != -1) {
+			return entry->current_index;
+		    }
 		}
+		break;
 	    }
-	    break;
 	}
     }
 
     zip_error_set(error, ZIP_ER_NOENT, 0);
-    return -1;    
+    return -1;
 }
 
-void
-_zip_hash_revert(zip_hash_t *hash)
-{
-    zip_uint16_t i;
+
+bool
+_zip_hash_reserve_capacity(zip_hash_t *hash, zip_uint64_t capacity, zip_error_t *error) {
+    zip_uint32_t new_size;
+
+    if (capacity == 0) {
+	return true;
+    }
+
+    new_size = size_for_capacity(capacity);
+
+    if (new_size <= hash->table_size) {
+	return true;
+    }
+
+    if (!hash_resize(hash, new_size, error)) {
+	return false;
+    }
+
+    return true;
+}
+
+
+bool
+_zip_hash_revert(zip_hash_t *hash, zip_error_t *error) {
+    zip_uint32_t i;
     zip_hash_entry_t *entry, *previous;
-    
+
     for (i = 0; i < hash->table_size; i++) {
 	previous = NULL;
 	entry = hash->table[i];
@@ -256,6 +386,7 @@ _zip_hash_revert(zip_hash_t *hash)
 		entry = entry->next;
 		/* previous does not change */
 		free(p);
+		hash->nentries--;
 	    }
 	    else {
 		entry->current_index = entry->orig_index;
@@ -264,4 +395,16 @@ _zip_hash_revert(zip_hash_t *hash)
 	    }
 	}
     }
+
+    if (hash->nentries < hash->table_size * HASH_MIN_FILL && hash->table_size > HASH_MIN_SIZE) {
+	zip_uint32_t new_size = hash->table_size / 2;
+	while (hash->nentries < new_size * HASH_MIN_FILL && new_size > HASH_MIN_SIZE) {
+	    new_size /= 2;
+	}
+	if (!hash_resize(hash, new_size, error)) {
+	    return false;
+	}
+    }
+
+    return true;
 }