Make name hash table resize automatically. Also, make it more efficient by keeping the full 32 bit hash value.
diff --git a/lib/zip_hash.c b/lib/zip_hash.c index ebe17fc..fc854a8 100644 --- a/lib/zip_hash.c +++ b/lib/zip_hash.c
@@ -35,94 +35,181 @@ #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_uint32_t table_size; + zip_uint64_t nentries; zip_hash_entry_t **table; }; + +/* 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 (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 false; + } + + 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_uint32_t table_size, zip_error_t *error) +_zip_hash_new(zip_error_t *error) { zip_hash_t *hash; - if (table_size == 0) { - zip_error_set(error, ZIP_ER_INTERNAL, 0); - return NULL; + if ((hash = (zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) { + zip_error_set(error, ZIP_ER_MEMORY, 0); + return NULL; } - if ((hash=(zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) { - zip_error_set(error, ZIP_ER_MEMORY, 0); - return NULL; - } - hash->table_size = table_size; - if ((hash->table=(zip_hash_entry_t**)calloc(table_size, sizeof(zip_hash_entry_t *))) == NULL) { - free(hash); - 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_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_uint32_t hash_value, table_index; zip_hash_entry_t *entry; if (hash == NULL || name == NULL || index > ZIP_INT64_MAX) { @@ -130,43 +217,59 @@ 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 (((flags & ZIP_FL_UNCHANGED) && entry->orig_index != -1) || entry->current_index != -1) { - zip_error_set(error, ZIP_ER_EXISTS, 0); - return false; - } - else { - break; - } + 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; + } + else { + break; + } + } + } + if (entry == NULL) { - if ((entry=(zip_hash_entry_t *)malloc(sizeof(zip_hash_entry_t))) == NULL) { - zip_error_set(error, ZIP_ER_MEMORY, 0); - return false; + 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[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; + } } - entry->name = name; - entry->next = hash->table[hash_value]; - hash->table[hash_value] = entry; - entry->orig_index = -1; } if (flags & ZIP_FL_UNCHANGED) { - entry->orig_index = (zip_int64_t)index; + entry->orig_index = (zip_int64_t)index; } entry->current_index = (zip_int64_t)index; 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_uint32_t hash_value, index; zip_hash_entry_t *entry, *previous; if (hash == NULL || name == NULL) { @@ -174,94 +277,144 @@ 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_uint32_t hash_value, index; zip_hash_entry_t *entry; if (hash == NULL || name == NULL) { - zip_error_set(error, ZIP_ER_INVAL, 0); - return -1; + zip_error_set(error, ZIP_ER_INVAL, 0); + 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) + +bool +_zip_hash_reserve_capacity(zip_hash_t *hash, zip_uint64_t capacity, zip_error_t *error) { - zip_uint16_t i; + 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]; - while (entry) { - if (entry->orig_index == -1) { - zip_hash_entry_t *p; - if (previous) { - previous->next = entry->next; - } - else { - hash->table[i] = entry->next; - } - p = entry; - entry = entry->next; - /* previous does not change */ - free(p); - } - else { - entry->current_index = entry->orig_index; - previous = entry; - entry = entry->next; - } + previous = NULL; + entry = hash->table[i]; + while (entry) { + if (entry->orig_index == -1) { + zip_hash_entry_t *p; + if (previous) { + previous->next = entry->next; + } + else { + hash->table[i] = entry->next; + } + p = entry; + entry = entry->next; + /* previous does not change */ + free(p); + hash->nentries--; + } + else { + entry->current_index = entry->orig_index; + previous = entry; + entry = entry->next; + } + } + } + + 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; }
diff --git a/lib/zip_new.c b/lib/zip_new.c index c05c2a3..a257a0d 100644 --- a/lib/zip_new.c +++ b/lib/zip_new.c
@@ -52,7 +52,7 @@ return NULL; } - if ((za->names = _zip_hash_new(ZIP_HASH_TABLE_SIZE, error)) == NULL) { + if ((za->names = _zip_hash_new(error)) == NULL) { free(za); return NULL; }
diff --git a/lib/zip_open.c b/lib/zip_open.c index f62f95f..e4e9d97 100644 --- a/lib/zip_open.c +++ b/lib/zip_open.c
@@ -212,6 +212,8 @@ free(cdir); + _zip_hash_reserve_capacity(za->names, za->nentry, &za->error); + for (idx = 0; idx < za->nentry; idx++) { const zip_uint8_t *name = _zip_string_get(za->entry[idx].orig->filename, NULL, 0, error); if (name == NULL) {
diff --git a/lib/zip_unchange_all.c b/lib/zip_unchange_all.c index 2221d6c..39754b2 100644 --- a/lib/zip_unchange_all.c +++ b/lib/zip_unchange_all.c
@@ -43,7 +43,9 @@ int ret; zip_uint64_t i; - _zip_hash_revert(za->names); + if (!_zip_hash_revert(za->names, &za->error)) { + return -1; + } ret = 0; for (i=0; i<za->nentry; i++)
diff --git a/lib/zipint.h b/lib/zipint.h index c64a1a2..6883c3a 100644 --- a/lib/zipint.h +++ b/lib/zipint.h
@@ -196,10 +196,6 @@ typedef enum zip_encoding_type zip_encoding_type_t; -#ifndef ZIP_HASH_TABLE_SIZE -#define ZIP_HASH_TABLE_SIZE 8192 -#endif - struct zip_hash; typedef struct zip_cdir zip_cdir_t; @@ -486,8 +482,9 @@ bool _zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *key, zip_error_t *error); void _zip_hash_free(zip_hash_t *hash); zip_int64_t _zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, zip_error_t *error); -zip_hash_t *_zip_hash_new(zip_uint32_t hash_size, zip_error_t *error); -void _zip_hash_revert(zip_hash_t *hash); +zip_hash_t *_zip_hash_new(zip_error_t *error); +bool _zip_hash_reserve_capacity(zip_hash_t *hash, zip_uint64_t capacity, zip_error_t *error); +bool _zip_hash_revert(zip_hash_t *hash, zip_error_t *error); zip_t *_zip_open(zip_source_t *, unsigned int, zip_error_t *);