VeraCrypt
aboutsummaryrefslogtreecommitdiff
path: root/src/Common/libzip/zip_hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/Common/libzip/zip_hash.c')
-rw-r--r--src/Common/libzip/zip_hash.c294
1 files changed, 147 insertions, 147 deletions
diff --git a/src/Common/libzip/zip_hash.c b/src/Common/libzip/zip_hash.c
index 3206dbf7..d3a954ec 100644
--- a/src/Common/libzip/zip_hash.c
+++ b/src/Common/libzip/zip_hash.c
@@ -1,9 +1,9 @@
/*
zip_hash.c -- hash table string -> uint64
- Copyright (C) 2015-2019 Dieter Baron and Thomas Klausner
+ Copyright (C) 2015-2021 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>
+ The authors can be contacted at <info@libzip.org>
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
@@ -67,9 +67,9 @@ struct zip_hash {
static void
free_list(zip_hash_entry_t *entry) {
while (entry != NULL) {
- zip_hash_entry_t *next = entry->next;
- free(entry);
- entry = next;
+ zip_hash_entry_t *next = entry->next;
+ free(entry);
+ entry = next;
}
}
@@ -80,12 +80,12 @@ hash_string(const zip_uint8_t *name) {
zip_uint64_t value = HASH_START;
if (name == NULL) {
- return 0;
+ return 0;
}
while (*name != 0) {
- value = (zip_uint64_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % 0x100000000ul);
- name++;
+ value = (zip_uint64_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % 0x100000000ul);
+ name++;
}
return (zip_uint32_t)value;
@@ -98,30 +98,30 @@ 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;
+ 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;
+ zip_error_set(error, ZIP_ER_MEMORY, 0);
+ return false;
}
if (hash->nentries > 0) {
- zip_uint32_t i;
+ 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;
+ 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;
+ zip_uint32_t new_index = entry->hash_value % new_size;
- entry->next = new_table[new_index];
- new_table[new_index] = entry;
+ entry->next = new_table[new_index];
+ new_table[new_index] = entry;
- entry = next;
- }
- }
+ entry = next;
+ }
+ }
}
free(hash->table);
@@ -138,14 +138,14 @@ size_for_capacity(zip_uint64_t capacity) {
zip_uint32_t v;
if (needed_size > ZIP_UINT32_MAX) {
- v = ZIP_UINT32_MAX;
+ v = ZIP_UINT32_MAX;
}
else {
- v = (zip_uint32_t)needed_size;
+ v = (zip_uint32_t)needed_size;
}
if (v > HASH_MAX_SIZE) {
- return HASH_MAX_SIZE;
+ return HASH_MAX_SIZE;
}
/* From Bit Twiddling Hacks by Sean Eron Anderson <seander@cs.stanford.edu>
@@ -168,8 +168,8 @@ _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;
+ zip_error_set(error, ZIP_ER_MEMORY, 0);
+ return NULL;
}
hash->table_size = 0;
@@ -185,16 +185,16 @@ _zip_hash_free(zip_hash_t *hash) {
zip_uint32_t i;
if (hash == NULL) {
- return;
+ return;
}
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);
+ for (i = 0; i < hash->table_size; i++) {
+ if (hash->table[i] != NULL) {
+ free_list(hash->table[i]);
+ }
+ }
+ free(hash->table);
}
free(hash);
}
@@ -207,51 +207,51 @@ _zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip
zip_hash_entry_t *entry;
if (hash == NULL || name == NULL || index > ZIP_INT64_MAX) {
- zip_error_set(error, ZIP_ER_INVAL, 0);
- return false;
+ zip_error_set(error, ZIP_ER_INVAL, 0);
+ return false;
}
if (hash->table_size == 0) {
- if (!hash_resize(hash, HASH_MIN_SIZE, error)) {
- return false;
- }
+ 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->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;
- }
- 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;
- }
- }
+ 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;
+ }
+ }
}
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;
@@ -266,40 +266,40 @@ _zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error)
zip_hash_entry_t *entry, *previous;
if (hash == NULL || name == NULL) {
- zip_error_set(error, ZIP_ER_INVAL, 0);
- return false;
+ zip_error_set(error, ZIP_ER_INVAL, 0);
+ return false;
}
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 {
- entry->current_index = -1;
- }
- return true;
- }
- previous = entry;
- entry = entry->next;
- }
+ 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 {
+ entry->current_index = -1;
+ }
+ return true;
+ }
+ previous = entry;
+ entry = entry->next;
+ }
}
zip_error_set(error, ZIP_ER_NOENT, 0);
@@ -314,28 +314,28 @@ _zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, z
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;
}
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;
- }
- }
- break;
- }
- }
+ 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;
+ }
+ }
+ break;
+ }
+ }
}
zip_error_set(error, ZIP_ER_NOENT, 0);
@@ -348,17 +348,17 @@ _zip_hash_reserve_capacity(zip_hash_t *hash, zip_uint64_t capacity, zip_error_t
zip_uint32_t new_size;
if (capacity == 0) {
- return true;
+ return true;
}
new_size = size_for_capacity(capacity);
if (new_size <= hash->table_size) {
- return true;
+ return true;
}
if (!hash_resize(hash, new_size, error)) {
- return false;
+ return false;
}
return true;
@@ -371,39 +371,39 @@ _zip_hash_revert(zip_hash_t *hash, zip_error_t *error) {
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);
- hash->nentries--;
- }
- 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;
- }
+ 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;