2 zip_hash.c -- hash table string -> uint64
3 Copyright (C) 2015-2016 Dieter Baron and Thomas Klausner
5 This file is part of libzip, a library to manipulate ZIP archives.
6 The authors can be contacted at <libzip@nih.at>
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions
11 1. Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 2. Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in
15 the documentation and/or other materials provided with the
17 3. The names of the authors may not be used to endorse or promote
18 products derived from this software without specific prior
21 THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS
22 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
25 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
27 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
29 IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
30 OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
31 IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 /* parameter for the string hash function */
39 #define HASH_MULTIPLIER 33
40 #define HASH_START 5381
42 /* hash table's fill ratio is kept between these by doubling/halfing its size as necessary */
43 #define HASH_MAX_FILL .75
44 #define HASH_MIN_FILL .01
46 /* but hash table size is kept between these */
47 #define HASH_MIN_SIZE 256
48 #define HASH_MAX_SIZE 0x80000000ul
50 struct zip_hash_entry {
51 const zip_uint8_t *name;
52 zip_int64_t orig_index;
53 zip_int64_t current_index;
54 struct zip_hash_entry *next;
55 zip_uint32_t hash_value;
57 typedef struct zip_hash_entry zip_hash_entry_t;
60 zip_uint32_t table_size;
61 zip_uint64_t nentries;
62 zip_hash_entry_t **table;
66 /* free list of entries */
68 free_list(zip_hash_entry_t *entry)
70 while (entry != NULL) {
71 zip_hash_entry_t *next = entry->next;
78 /* compute hash of string, full 32 bit value */
80 hash_string(const zip_uint8_t *name)
82 zip_uint64_t value = HASH_START;
89 value = (zip_uint64_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % 0x100000000ul);
93 return (zip_uint32_t)value;
97 /* resize hash table; new_size must be a power of 2, can be larger or smaller than current size */
99 hash_resize(zip_hash_t *hash, zip_uint32_t new_size, zip_error_t *error)
101 zip_hash_entry_t **new_table;
103 if (new_size == hash->table_size) {
107 if ((new_table = (zip_hash_entry_t**)calloc(new_size, sizeof(zip_hash_entry_t *))) == NULL) {
108 zip_error_set(error, ZIP_ER_MEMORY, 0);
112 if (hash->nentries > 0) {
115 for (i = 0; i < hash->table_size; i++) {
116 zip_hash_entry_t *entry = hash->table[i];
118 zip_hash_entry_t *next = entry->next;
120 zip_uint32_t new_index = entry->hash_value % new_size;
122 entry->next = new_table[new_index];
123 new_table[new_index] = entry;
131 hash->table = new_table;
132 hash->table_size = new_size;
139 size_for_capacity(zip_uint64_t capacity) {
140 double needed_size = capacity / HASH_MAX_FILL;
143 if (needed_size > ZIP_UINT32_MAX) {
147 v = (zip_uint32_t)needed_size;
150 if (v > HASH_MAX_SIZE) {
151 return HASH_MAX_SIZE;
154 /* From Bit Twiddling Hacks by Sean Eron Anderson <seander@cs.stanford.edu>
155 (http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2). */
170 _zip_hash_new(zip_error_t *error)
174 if ((hash = (zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) {
175 zip_error_set(error, ZIP_ER_MEMORY, 0);
179 hash->table_size = 0;
188 _zip_hash_free(zip_hash_t *hash)
196 if (hash->table != NULL) {
197 for (i=0; i<hash->table_size; i++) {
198 if (hash->table[i] != NULL) {
199 free_list(hash->table[i]);
208 /* insert into hash, return error on existence or memory issues */
210 _zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip_flags_t flags, zip_error_t *error)
212 zip_uint32_t hash_value, table_index;
213 zip_hash_entry_t *entry;
215 if (hash == NULL || name == NULL || index > ZIP_INT64_MAX) {
216 zip_error_set(error, ZIP_ER_INVAL, 0);
220 if (hash->table_size == 0) {
221 if (!hash_resize(hash, HASH_MIN_SIZE, error)) {
226 hash_value = hash_string(name);
227 table_index = hash_value % hash->table_size;
229 for (entry = hash->table[table_index]; entry != NULL; entry = entry->next) {
230 if (entry->hash_value == hash_value && strcmp((const char *)name, (const char *)entry->name) == 0) {
231 if (((flags & ZIP_FL_UNCHANGED) && entry->orig_index != -1) || entry->current_index != -1) {
232 zip_error_set(error, ZIP_ER_EXISTS, 0);
242 if ((entry = (zip_hash_entry_t *)malloc(sizeof(zip_hash_entry_t))) == NULL) {
243 zip_error_set(error, ZIP_ER_MEMORY, 0);
247 entry->next = hash->table[table_index];
248 hash->table[table_index] = entry;
249 entry->hash_value = hash_value;
250 entry->orig_index = -1;
252 if (hash->nentries > hash->table_size * HASH_MAX_FILL && hash->table_size < HASH_MAX_SIZE) {
253 if (!hash_resize(hash, hash->table_size * 2, error)) {
259 if (flags & ZIP_FL_UNCHANGED) {
260 entry->orig_index = (zip_int64_t)index;
262 entry->current_index = (zip_int64_t)index;
268 /* remove entry from hash, error if not found */
270 _zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error)
272 zip_uint32_t hash_value, index;
273 zip_hash_entry_t *entry, *previous;
275 if (hash == NULL || name == NULL) {
276 zip_error_set(error, ZIP_ER_INVAL, 0);
280 if (hash->nentries > 0) {
281 hash_value = hash_string(name);
282 index = hash_value % hash->table_size;
284 entry = hash->table[index];
286 if (entry->hash_value == hash_value && strcmp((const char *)name, (const char *)entry->name) == 0) {
287 if (entry->orig_index == -1) {
289 previous->next = entry->next;
292 hash->table[index] = entry->next;
296 if (hash->nentries < hash->table_size * HASH_MIN_FILL && hash->table_size > HASH_MIN_SIZE) {
297 if (!hash_resize(hash, hash->table_size / 2, error)) {
303 entry->current_index = -1;
312 zip_error_set(error, ZIP_ER_NOENT, 0);
317 /* find value for entry in hash, -1 if not found */
319 _zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, zip_error_t *error)
321 zip_uint32_t hash_value, index;
322 zip_hash_entry_t *entry;
324 if (hash == NULL || name == NULL) {
325 zip_error_set(error, ZIP_ER_INVAL, 0);
329 if (hash->nentries > 0) {
330 hash_value = hash_string(name);
331 index = hash_value % hash->table_size;
332 for (entry = hash->table[index]; entry != NULL; entry = entry->next) {
333 if (strcmp((const char *)name, (const char *)entry->name) == 0) {
334 if (flags & ZIP_FL_UNCHANGED) {
335 if (entry->orig_index != -1) {
336 return entry->orig_index;
340 if (entry->current_index != -1) {
341 return entry->current_index;
349 zip_error_set(error, ZIP_ER_NOENT, 0);
355 _zip_hash_reserve_capacity(zip_hash_t *hash, zip_uint64_t capacity, zip_error_t *error)
357 zip_uint32_t new_size;
363 new_size = size_for_capacity(capacity);
365 if (new_size <= hash->table_size) {
369 if (!hash_resize(hash, new_size, error)) {
378 _zip_hash_revert(zip_hash_t *hash, zip_error_t *error)
381 zip_hash_entry_t *entry, *previous;
383 for (i = 0; i < hash->table_size; i++) {
385 entry = hash->table[i];
387 if (entry->orig_index == -1) {
390 previous->next = entry->next;
393 hash->table[i] = entry->next;
397 /* previous does not change */
402 entry->current_index = entry->orig_index;
409 if (hash->nentries < hash->table_size * HASH_MIN_FILL && hash->table_size > HASH_MIN_SIZE) {
410 zip_uint32_t new_size = hash->table_size / 2;
411 while (hash->nentries < new_size * HASH_MIN_FILL && new_size > HASH_MIN_SIZE) {
414 if (!hash_resize(hash, new_size, error)) {