xref: /PHP-7.2/ext/zip/lib/zip_hash.c (revision dac6c639)
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