1 /*
2 zip_hash.c -- hash table string -> uint64
3 Copyright (c) 2015-2017 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 struct zip_hash_entry {
39 const zip_uint8_t *name;
40 zip_int64_t orig_index;
41 zip_int64_t current_index;
42 struct zip_hash_entry *next;
43 };
44 typedef struct zip_hash_entry zip_hash_entry_t;
45
46 struct zip_hash {
47 zip_uint16_t table_size;
48 zip_hash_entry_t **table;
49 };
50
51 zip_hash_t *
_zip_hash_new(zip_uint16_t table_size,zip_error_t * error)52 _zip_hash_new(zip_uint16_t table_size, zip_error_t *error)
53 {
54 zip_hash_t *hash;
55
56 if (table_size == 0) {
57 zip_error_set(error, ZIP_ER_INTERNAL, 0);
58 return NULL;
59 }
60
61 if ((hash=(zip_hash_t *)malloc(sizeof(zip_hash_t))) == NULL) {
62 zip_error_set(error, ZIP_ER_MEMORY, 0);
63 return NULL;
64 }
65 hash->table_size = table_size;
66 if ((hash->table=(zip_hash_entry_t**)calloc(table_size, sizeof(zip_hash_entry_t *))) == NULL) {
67 free(hash);
68 zip_error_set(error, ZIP_ER_MEMORY, 0);
69 return NULL;
70 }
71
72 return hash;
73 }
74
75 static void
_free_list(zip_hash_entry_t * entry)76 _free_list(zip_hash_entry_t *entry)
77 {
78 zip_hash_entry_t *next;
79 do {
80 next = entry->next;
81 free(entry);
82 entry = next;
83 } while (entry != NULL);
84 }
85
86 void
_zip_hash_free(zip_hash_t * hash)87 _zip_hash_free(zip_hash_t *hash)
88 {
89 zip_uint16_t i;
90
91 if (hash == NULL) {
92 return;
93 }
94
95 for (i=0; i<hash->table_size; i++) {
96 if (hash->table[i] != NULL) {
97 _free_list(hash->table[i]);
98 }
99 }
100 free(hash->table);
101 free(hash);
102 }
103
104 static zip_uint16_t
_hash_string(const zip_uint8_t * name,zip_uint16_t size)105 _hash_string(const zip_uint8_t *name, zip_uint16_t size)
106 {
107 #define HASH_MULTIPLIER 33
108 zip_uint16_t value = 5381;
109
110 if (name == NULL)
111 return 0;
112
113 while (*name != 0) {
114 value = (zip_uint16_t)(((value * HASH_MULTIPLIER) + (zip_uint8_t)*name) % size);
115 name++;
116 }
117
118 return value;
119 }
120
121 /* insert into hash, return error on existence or memory issues */
122 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)123 _zip_hash_add(zip_hash_t *hash, const zip_uint8_t *name, zip_uint64_t index, zip_flags_t flags, zip_error_t *error)
124 {
125 zip_uint16_t hash_value;
126 zip_hash_entry_t *entry;
127
128 if (hash == NULL || name == NULL || index > ZIP_INT64_MAX) {
129 zip_error_set(error, ZIP_ER_INVAL, 0);
130 return false;
131 }
132
133 hash_value = _hash_string(name, hash->table_size);
134 for (entry = hash->table[hash_value]; entry != NULL; entry = entry->next) {
135 if (strcmp((const char *)name, (const char *)entry->name) == 0) {
136 if (((flags & ZIP_FL_UNCHANGED) && entry->orig_index != -1) || entry->current_index != -1) {
137 zip_error_set(error, ZIP_ER_EXISTS, 0);
138 return false;
139 }
140 else {
141 break;
142 }
143 }
144 }
145
146 if (entry == NULL) {
147 if ((entry=(zip_hash_entry_t *)malloc(sizeof(zip_hash_entry_t))) == NULL) {
148 zip_error_set(error, ZIP_ER_MEMORY, 0);
149 return false;
150 }
151 entry->name = name;
152 entry->next = hash->table[hash_value];
153 hash->table[hash_value] = entry;
154 entry->orig_index = -1;
155 }
156
157 if (flags & ZIP_FL_UNCHANGED) {
158 entry->orig_index = (zip_int64_t)index;
159 }
160 entry->current_index = (zip_int64_t)index;
161
162 return true;
163 }
164
165 /* remove entry from hash, error if not found */
166 bool
_zip_hash_delete(zip_hash_t * hash,const zip_uint8_t * name,zip_error_t * error)167 _zip_hash_delete(zip_hash_t *hash, const zip_uint8_t *name, zip_error_t *error)
168 {
169 zip_uint16_t hash_value;
170 zip_hash_entry_t *entry, *previous;
171
172 if (hash == NULL || name == NULL) {
173 zip_error_set(error, ZIP_ER_INVAL, 0);
174 return false;
175 }
176
177 hash_value = _hash_string(name, hash->table_size);
178 previous = NULL;
179 entry = hash->table[hash_value];
180 while (entry) {
181 if (strcmp((const char *)name, (const char *)entry->name) == 0) {
182 if (entry->orig_index == -1) {
183 if (previous) {
184 previous->next = entry->next;
185 }
186 else {
187 hash->table[hash_value] = entry->next;
188 }
189 free(entry);
190 }
191 else {
192 entry->current_index = -1;
193 }
194 return true;
195 }
196 previous = entry;
197 entry = entry->next;
198 };
199
200 zip_error_set(error, ZIP_ER_NOENT, 0);
201 return false;
202 }
203
204 /* find value for entry in hash, -1 if not found */
205 zip_int64_t
_zip_hash_lookup(zip_hash_t * hash,const zip_uint8_t * name,zip_flags_t flags,zip_error_t * error)206 _zip_hash_lookup(zip_hash_t *hash, const zip_uint8_t *name, zip_flags_t flags, zip_error_t *error)
207 {
208 zip_uint16_t hash_value;
209 zip_hash_entry_t *entry;
210
211 if (hash == NULL || name == NULL) {
212 zip_error_set(error, ZIP_ER_INVAL, 0);
213 return -1;
214 }
215
216 hash_value = _hash_string(name, hash->table_size);
217 for (entry = hash->table[hash_value]; entry != NULL; entry = entry->next) {
218 if (strcmp((const char *)name, (const char *)entry->name) == 0) {
219 if (flags & ZIP_FL_UNCHANGED) {
220 if (entry->orig_index != -1) {
221 return entry->orig_index;
222 }
223 }
224 else {
225 if (entry->current_index != -1) {
226 return entry->current_index;
227 }
228 }
229 break;
230 }
231 }
232
233 zip_error_set(error, ZIP_ER_NOENT, 0);
234 return -1;
235 }
236
237 void
_zip_hash_revert(zip_hash_t * hash)238 _zip_hash_revert(zip_hash_t *hash)
239 {
240 zip_uint16_t i;
241 zip_hash_entry_t *entry, *previous;
242
243 for (i = 0; i < hash->table_size; i++) {
244 previous = NULL;
245 entry = hash->table[i];
246 while (entry) {
247 if (entry->orig_index == -1) {
248 zip_hash_entry_t *p;
249 if (previous) {
250 previous->next = entry->next;
251 }
252 else {
253 hash->table[i] = entry->next;
254 }
255 p = entry;
256 entry = entry->next;
257 /* previous does not change */
258 free(p);
259 }
260 else {
261 entry->current_index = entry->orig_index;
262 previous = entry;
263 entry = entry->next;
264 }
265 }
266 }
267 }
268
