1 /***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) 1998 - 2016, Daniel Stenberg, <daniel@haxx.se>, et al.
9 *
10 * This software is licensed as described in the file COPYING, which
11 * you should have received as part of this distribution. The terms
12 * are also available at https://curl.haxx.se/docs/copyright.html.
13 *
14 * You may opt to use, copy, modify, merge, publish, distribute and/or sell
15 * copies of the Software, and permit persons to whom the Software is
16 * furnished to do so, under the terms of the COPYING file.
17 *
18 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19 * KIND, either express or implied.
20 *
21 ***************************************************************************/
22
23 #include "curl_setup.h"
24
25 #include <curl/curl.h>
26
27 #include "hash.h"
28 #include "llist.h"
29 #include "curl_memory.h"
30
31 /* The last #include file should be: */
32 #include "memdebug.h"
33
34 static void
hash_element_dtor(void * user,void * element)35 hash_element_dtor(void *user, void *element)
36 {
37 struct curl_hash *h = (struct curl_hash *) user;
38 struct curl_hash_element *e = (struct curl_hash_element *) element;
39
40 Curl_safefree(e->key);
41
42 if(e->ptr) {
43 h->dtor(e->ptr);
44 e->ptr = NULL;
45 }
46
47 e->key_len = 0;
48
49 free(e);
50 }
51
52 /* Initializes a hash structure.
53 * Return 1 on error, 0 is fine.
54 *
55 * @unittest: 1602
56 * @unittest: 1603
57 */
58 int
Curl_hash_init(struct curl_hash * h,int slots,hash_function hfunc,comp_function comparator,curl_hash_dtor dtor)59 Curl_hash_init(struct curl_hash *h,
60 int slots,
61 hash_function hfunc,
62 comp_function comparator,
63 curl_hash_dtor dtor)
64 {
65 int i;
66
67 if(!slots || !hfunc || !comparator ||!dtor) {
68 return 1; /* failure */
69 }
70
71 h->hash_func = hfunc;
72 h->comp_func = comparator;
73 h->dtor = dtor;
74 h->size = 0;
75 h->slots = slots;
76
77 h->table = malloc(slots * sizeof(struct curl_llist *));
78 if(h->table) {
79 for(i = 0; i < slots; ++i) {
80 h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
81 if(!h->table[i]) {
82 while(i--) {
83 Curl_llist_destroy(h->table[i], NULL);
84 h->table[i] = NULL;
85 }
86 free(h->table);
87 h->table = NULL;
88 h->slots = 0;
89 return 1; /* failure */
90 }
91 }
92 return 0; /* fine */
93 }
94 else {
95 h->slots = 0;
96 return 1; /* failure */
97 }
98 }
99
100 static struct curl_hash_element *
mk_hash_element(const void * key,size_t key_len,const void * p)101 mk_hash_element(const void *key, size_t key_len, const void *p)
102 {
103 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element));
104
105 if(he) {
106 void *dupkey = malloc(key_len);
107 if(dupkey) {
108 /* copy the key */
109 memcpy(dupkey, key, key_len);
110
111 he->key = dupkey;
112 he->key_len = key_len;
113 he->ptr = (void *) p;
114 }
115 else {
116 /* failed to duplicate the key, free memory and fail */
117 free(he);
118 he = NULL;
119 }
120 }
121 return he;
122 }
123
124 #define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)]
125
126 /* Insert the data in the hash. If there already was a match in the hash,
127 * that data is replaced.
128 *
129 * @unittest: 1305
130 * @unittest: 1602
131 * @unittest: 1603
132 */
133 void *
Curl_hash_add(struct curl_hash * h,void * key,size_t key_len,void * p)134 Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
135 {
136 struct curl_hash_element *he;
137 struct curl_llist_element *le;
138 struct curl_llist *l = FETCH_LIST (h, key, key_len);
139
140 for(le = l->head; le; le = le->next) {
141 he = (struct curl_hash_element *) le->ptr;
142 if(h->comp_func(he->key, he->key_len, key, key_len)) {
143 Curl_llist_remove(l, le, (void *)h);
144 --h->size;
145 break;
146 }
147 }
148
149 he = mk_hash_element(key, key_len, p);
150 if(he) {
151 if(Curl_llist_insert_next(l, l->tail, he)) {
152 ++h->size;
153 return p; /* return the new entry */
154 }
155 /*
156 * Couldn't insert it, destroy the 'he' element and the key again. We
157 * don't call hash_element_dtor() since that would also call the
158 * "destructor" for the actual data 'p'. When we fail, we shall not touch
159 * that data.
160 */
161 free(he->key);
162 free(he);
163 }
164
165 return NULL; /* failure */
166 }
167
168 /* Remove the identified hash entry.
169 * Returns non-zero on failure.
170 *
171 * @unittest: 1603
172 */
Curl_hash_delete(struct curl_hash * h,void * key,size_t key_len)173 int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
174 {
175 struct curl_llist_element *le;
176 struct curl_hash_element *he;
177 struct curl_llist *l = FETCH_LIST(h, key, key_len);
178
179 for(le = l->head; le; le = le->next) {
180 he = le->ptr;
181 if(h->comp_func(he->key, he->key_len, key, key_len)) {
182 Curl_llist_remove(l, le, (void *) h);
183 --h->size;
184 return 0;
185 }
186 }
187 return 1;
188 }
189
190 /* Retrieves a hash element.
191 *
192 * @unittest: 1603
193 */
194 void *
Curl_hash_pick(struct curl_hash * h,void * key,size_t key_len)195 Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
196 {
197 struct curl_llist_element *le;
198 struct curl_hash_element *he;
199 struct curl_llist *l;
200
201 if(h) {
202 l = FETCH_LIST(h, key, key_len);
203 for(le = l->head; le; le = le->next) {
204 he = le->ptr;
205 if(h->comp_func(he->key, he->key_len, key, key_len)) {
206 return he->ptr;
207 }
208 }
209 }
210
211 return NULL;
212 }
213
214 #if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
215 void
Curl_hash_apply(curl_hash * h,void * user,void (* cb)(void * user,void * ptr))216 Curl_hash_apply(curl_hash *h, void *user,
217 void (*cb)(void *user, void *ptr))
218 {
219 struct curl_llist_element *le;
220 int i;
221
222 for(i = 0; i < h->slots; ++i) {
223 for(le = (h->table[i])->head;
224 le;
225 le = le->next) {
226 curl_hash_element *el = le->ptr;
227 cb(user, el->ptr);
228 }
229 }
230 }
231 #endif
232
233 /* Destroys all the entries in the given hash and resets its attributes,
234 * prepping the given hash for [static|dynamic] deallocation.
235 *
236 * @unittest: 1305
237 * @unittest: 1602
238 * @unittest: 1603
239 */
240 void
Curl_hash_destroy(struct curl_hash * h)241 Curl_hash_destroy(struct curl_hash *h)
242 {
243 int i;
244
245 for(i = 0; i < h->slots; ++i) {
246 Curl_llist_destroy(h->table[i], (void *) h);
247 h->table[i] = NULL;
248 }
249
250 Curl_safefree(h->table);
251 h->size = 0;
252 h->slots = 0;
253 }
254
255 /* Removes all the entries in the given hash.
256 *
257 * @unittest: 1602
258 */
259 void
Curl_hash_clean(struct curl_hash * h)260 Curl_hash_clean(struct curl_hash *h)
261 {
262 Curl_hash_clean_with_criterium(h, NULL, NULL);
263 }
264
265 /* Cleans all entries that pass the comp function criteria. */
266 void
Curl_hash_clean_with_criterium(struct curl_hash * h,void * user,int (* comp)(void *,void *))267 Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
268 int (*comp)(void *, void *))
269 {
270 struct curl_llist_element *le;
271 struct curl_llist_element *lnext;
272 struct curl_llist *list;
273 int i;
274
275 if(!h)
276 return;
277
278 for(i = 0; i < h->slots; ++i) {
279 list = h->table[i];
280 le = list->head; /* get first list entry */
281 while(le) {
282 struct curl_hash_element *he = le->ptr;
283 lnext = le->next;
284 /* ask the callback function if we shall remove this entry or not */
285 if(comp == NULL || comp(user, he->ptr)) {
286 Curl_llist_remove(list, le, (void *) h);
287 --h->size; /* one less entry in the hash now */
288 }
289 le = lnext;
290 }
291 }
292 }
293
Curl_hash_str(void * key,size_t key_length,size_t slots_num)294 size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num)
295 {
296 const char* key_str = (const char *) key;
297 const char *end = key_str + key_length;
298 unsigned long h = 5381;
299
300 while(key_str < end) {
301 h += h << 5;
302 h ^= (unsigned long) *key_str++;
303 }
304
305 return (h % slots_num);
306 }
307
Curl_str_key_compare(void * k1,size_t key1_len,void * k2,size_t key2_len)308 size_t Curl_str_key_compare(void *k1, size_t key1_len,
309 void *k2, size_t key2_len)
310 {
311 if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
312 return 1;
313
314 return 0;
315 }
316
Curl_hash_start_iterate(struct curl_hash * hash,struct curl_hash_iterator * iter)317 void Curl_hash_start_iterate(struct curl_hash *hash,
318 struct curl_hash_iterator *iter)
319 {
320 iter->hash = hash;
321 iter->slot_index = 0;
322 iter->current_element = NULL;
323 }
324
325 struct curl_hash_element *
Curl_hash_next_element(struct curl_hash_iterator * iter)326 Curl_hash_next_element(struct curl_hash_iterator *iter)
327 {
328 int i;
329 struct curl_hash *h = iter->hash;
330
331 /* Get the next element in the current list, if any */
332 if(iter->current_element)
333 iter->current_element = iter->current_element->next;
334
335 /* If we have reached the end of the list, find the next one */
336 if(!iter->current_element) {
337 for(i = iter->slot_index;i < h->slots;i++) {
338 if(h->table[i]->head) {
339 iter->current_element = h->table[i]->head;
340 iter->slot_index = i+1;
341 break;
342 }
343 }
344 }
345
346 if(iter->current_element) {
347 struct curl_hash_element *he = iter->current_element->ptr;
348 return he;
349 }
350 else {
351 iter->current_element = NULL;
352 return NULL;
353 }
354 }
355
356 #if 0 /* useful function for debugging hashes and their contents */
357 void Curl_hash_print(struct curl_hash *h,
358 void (*func)(void *))
359 {
360 struct curl_hash_iterator iter;
361 struct curl_hash_element *he;
362 int last_index = -1;
363
364 if(!h)
365 return;
366
367 fprintf(stderr, "=Hash dump=\n");
368
369 Curl_hash_start_iterate(h, &iter);
370
371 he = Curl_hash_next_element(&iter);
372 while(he) {
373 if(iter.slot_index != last_index) {
374 fprintf(stderr, "index %d:", iter.slot_index);
375 if(last_index >= 0) {
376 fprintf(stderr, "\n");
377 }
378 last_index = iter.slot_index;
379 }
380
381 if(func)
382 func(he->ptr);
383 else
384 fprintf(stderr, " [%p]", (void *)he->ptr);
385
386 he = Curl_hash_next_element(&iter);
387 }
388 fprintf(stderr, "\n");
389 }
390 #endif
391