lib/zip_hash.c

   1 /*
   2   zip_hash.c -- hash table string -> uint64
   3   Copyright (C) 2015-2016 Dieter Baron and Thomas Klausner
   4
   5   This file is part of libzip, a library to manipulate ZIP archives.
   6   The authors can be contacted at <libzip@nih.at>
   7
   8   Redistribution and use in source and binary forms, with or without
   9   modification, are permitted provided that the following conditions
  10   are met:
  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
  16      distribution.
  17   3. The names of the authors may not be used to endorse or promote
  18      products derived from this software without specific prior
  19      written permission.
  20
  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.
  32 */
  33
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #include "zipint.h"
  37
  38 /* parameter for the string hash function */
  39 #define HASH_MULTIPLIER 33
  40 #define HASH_START 5381
  41
  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
  45
  46 /* but hash table size is kept between these */
  47 #define HASH_MIN_SIZE 256
  48 #define HASH_MAX_SIZE 0x80000000ul
  49
  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;
  56 };
  57 typedef struct zip_hash_entry zip_hash_entry_t;
  58
  59 struct zip_hash {
  60     zip_uint32_t table_size;
  61     zip_uint64_t nentries;
  62     zip_hash_entry_t **table;
  63 };
  64
  65
  66 /* free list of entries */
  67 static void
  68 free_list(zip_hash_entry_t *entry)
  69 {
  70     while (entry != NULL) {
  71         zip_hash_entry_t *next = entry->next;
  72         free(entry);
  73         entry = next;
  74     }
  75 }
  76
  77
  78 /* compute hash of string, full 32 bit value */
  79 static zip_uint32_t
  80 hash_string(const zip_uint8_t *name)
  81 {
  82     zip_uint64_t value = HASH_START;
  83
  84     if (name == NULL) {
  85         return 0;
  86     }
  87
  88     while (*name != 0) {
  89         value = (zip_uint64_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % 0x100000000ul);
  90         name++;
  91     }
  92
  93     return (zip_uint32_t)value;
  94 }
  95
  96
  97 /* resize hash table; new_size must be a power of 2, can be larger or smaller than current size */
  98 static bool
  99 hash_resize(zip_hash_t *hash, zip_uint32_t new_size, zip_error_t *error)
 100 {
 101     zip_hash_entry_t **new_table;
 102
 103     if (new_size == hash->table_size) {
 104         return true;
 105     }
 106
 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);
 109         return false;
 110     }
 111
 112     if (hash->nentries > 0) {
 113         zip_uint32_t i;
 114
 115         for (i = 0; i < hash->table_size; i++) {
 116             zip_hash_entry_t *entry = hash->table[i];
 117             while (entry) {
 118                 zip_hash_entry_t *next = entry->next;
 119
 120                 zip_uint32_t new_index = entry->hash_value % new_size;
 121
 122                 entry->next = new_table[new_index];
 123                 new_table[new_index] = entry;
 124
 125                 entry = next;
 126             }
 127         }
 128     }
 129
 130     free(hash->table);
 131     hash->table = new_table;
 132     hash->table_size = new_size;
 133
 134     return true;
 135 }
 136
 137
 138 static zip_uint32_t
 139 size_for_capacity(zip_uint64_t capacity) {
 140     double needed_size = capacity / HASH_MAX_FILL;
 141     zip_uint32_t v;
 142
 143     if (needed_size > ZIP_UINT32_MAX) {
 144         v = ZIP_UINT32_MAX;
 145     }
 146     else {
 147         v = (zip_uint32_t)needed_size;
 148     }
 149
 150     if (v > HASH_MAX_SIZE) {
 151         return HASH_MAX_SIZE;
 152     }
 153
 154     /* From Bit Twiddling Hacks by Sean Eron Anderson <seander@cs.stanford.edu>
 155      (http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2). */
 156
 157     v--;
 158     v |= v >> 1;
 159     v |= v >> 2;
 160     v |= v >> 4;
 161     v |= v >> 8;
 162     v |= v >> 16;
 163     v++;
 164
 165     return v;
 166 }
 167
 168
 169 zip_hash_t *
 170 _zip_hash_new(zip_error_t *error)
 171 {
 172     zip_hash_t *hash;
 173
 174     if ((hash = (zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) {
 175         zip_error_set(error, ZIP_ER_MEMORY, 0);
 176         return NULL;
 177     }
 178
 179     hash->table_size = 0;
 180     hash->nentries = 0;
 181     hash->table = NULL;
 182
 183     return hash;
 184 }
 185
 186
 187 void
 188 _zip_hash_free(zip_hash_t *hash)
 189 {
 190     zip_uint32_t i;
 191
 192     if (hash == NULL) {
 193         return;
 194     }
 195
 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]);
 200             }
 201         }
 202         free(hash->table);
 203     }
 204     free(hash);
 205 }
 206
 207
 208 /* insert into hash, return error on existence or memory issues */
 209 bool
 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)
 211 {
 212     zip_uint32_t hash_value, table_index;
 213     zip_hash_entry_t *entry;
 214
 215     if (hash == NULL || name == NULL || index > ZIP_INT64_MAX) {
 216         zip_error_set(error, ZIP_ER_INVAL, 0);
 217         return false;
 218     }
 219
 220     if (hash->table_size == 0) {
 221         if (!hash_resize(hash, HASH_MIN_SIZE, error)) {
 222             return false;
 223         }
 224     }
 225
 226     hash_value = hash_string(name);
 227     table_index = hash_value % hash->table_size;
 228
 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);
 233                 return false;
 234             }
 235             else {
 236                 break;
 237             }
 238         }
 239     }
 240
 241     if (entry == NULL) {
 242         if ((entry = (zip_hash_entry_t *)malloc(sizeof(zip_hash_entry_t))) == NULL) {
 243             zip_error_set(error, ZIP_ER_MEMORY, 0);
 244             return false;
 245         }
 246         entry->name = name;
 247         entry->next = hash->table[table_index];
 248         hash->table[table_index] = entry;
 249         entry->hash_value = hash_value;
 250         entry->orig_index = -1;
 251         hash->nentries++;
 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)) {
 254                 return false;
 255             }
 256         }
 257     }
 258
 259     if (flags & ZIP_FL_UNCHANGED) {
 260         entry->orig_index = (zip_int64_t)index;
 261     }
 262     entry->current_index = (zip_int64_t)index;
 263
 264     return true;
 265 }
 266
 267
 268 /* remove entry from hash, error if not found */
 269 bool
 270 _zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error)
 271 {
 272     zip_uint32_t hash_value, index;
 273     zip_hash_entry_t *entry, *previous;
 274
 275     if (hash == NULL || name == NULL) {
 276         zip_error_set(error, ZIP_ER_INVAL, 0);
 277         return false;
 278     }
 279
 280     if (hash->nentries > 0) {
 281         hash_value = hash_string(name);
 282         index = hash_value % hash->table_size;
 283         previous = NULL;
 284         entry = hash->table[index];
 285         while (entry) {
 286             if (entry->hash_value == hash_value && strcmp((const char *)name, (const char *)entry->name) == 0) {
 287                 if (entry->orig_index == -1) {
 288                     if (previous) {
 289                         previous->next = entry->next;
 290                     }
 291                     else {
 292                         hash->table[index] = entry->next;
 293                     }
 294                     free(entry);
 295                     hash->nentries--;
 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)) {
 298                             return false;
 299                         }
 300                     }
 301                 }
 302                 else {
 303                     entry->current_index = -1;
 304                 }
 305                 return true;
 306             }
 307             previous = entry;
 308             entry = entry->next;
 309         }
 310     }
 311
 312     zip_error_set(error, ZIP_ER_NOENT, 0);
 313     return false;
 314 }
 315
 316
 317 /* find value for entry in hash, -1 if not found */
 318 zip_int64_t
 319 _zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, zip_error_t *error)
 320 {
 321     zip_uint32_t hash_value, index;
 322     zip_hash_entry_t *entry;
 323
 324     if (hash == NULL || name == NULL) {
 325         zip_error_set(error, ZIP_ER_INVAL, 0);
 326         return -1;
 327     }
 328
 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;
 337                     }
 338                 }
 339                 else {
 340                     if (entry->current_index != -1) {
 341                         return entry->current_index;
 342                     }
 343                 }
 344                 break;
 345             }
 346         }
 347     }
 348
 349     zip_error_set(error, ZIP_ER_NOENT, 0);
 350     return -1;
 351 }
 352
 353
 354 bool
 355 _zip_hash_reserve_capacity(zip_hash_t *hash, zip_uint64_t capacity, zip_error_t *error)
 356 {
 357     zip_uint32_t new_size;
 358
 359     if (capacity == 0) {
 360         return true;
 361     }
 362
 363     new_size = size_for_capacity(capacity);
 364
 365     if (new_size <= hash->table_size) {
 366         return true;
 367     }
 368
 369     if (!hash_resize(hash, new_size, error)) {
 370         return false;
 371     }
 372
 373     return true;
 374 }
 375
 376
 377 bool
 378 _zip_hash_revert(zip_hash_t *hash, zip_error_t *error)
 379 {
 380     zip_uint32_t i;
 381     zip_hash_entry_t *entry, *previous;
 382
 383     for (i = 0; i < hash->table_size; i++) {
 384         previous = NULL;
 385         entry = hash->table[i];
 386         while (entry) {
 387             if (entry->orig_index == -1) {
 388                 zip_hash_entry_t *p;
 389                 if (previous) {
 390                     previous->next = entry->next;
 391                 }
 392                 else {
 393                     hash->table[i] = entry->next;
 394                 }
 395                 p = entry;
 396                 entry = entry->next;
 397                 /* previous does not change */
 398                 free(p);
 399                 hash->nentries--;
 400             }
 401             else {
 402                 entry->current_index = entry->orig_index;
 403                 previous = entry;
 404                 entry = entry->next;
 405             }
 406         }
 407     }
 408
 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) {
 412             new_size /= 2;
 413         }
 414         if (!hash_resize(hash, new_size, error)) {
 415             return false;
 416         }
 417     }
 418
 419     return true;
 420 }