1 /***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) 1998 - 2017, 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 if(e->ptr) {
41 h->dtor(e->ptr);
42 e->ptr = NULL;
43 }
44
45 e->key_len = 0;
46
47 free(e);
48 }
49
50 /* Initializes a hash structure.
51 * Return 1 on error, 0 is fine.
52 *
53 * @unittest: 1602
54 * @unittest: 1603
55 */
56 int
Curl_hash_init(struct curl_hash * h,int slots,hash_function hfunc,comp_function comparator,curl_hash_dtor dtor)57 Curl_hash_init(struct curl_hash *h,
58 int slots,
59 hash_function hfunc,
60 comp_function comparator,
61 curl_hash_dtor dtor)
62 {
63 int i;
64
65 if(!slots || !hfunc || !comparator ||!dtor) {
66 return 1; /* failure */
67 }
68
69 h->hash_func = hfunc;
70 h->comp_func = comparator;
71 h->dtor = dtor;
72 h->size = 0;
73 h->slots = slots;
74
75 h->table = malloc(slots * sizeof(struct curl_llist));
76 if(h->table) {
77 for(i = 0; i < slots; ++i)
78 Curl_llist_init(&h->table[i], (curl_llist_dtor) hash_element_dtor);
79 return 0; /* fine */
80 }
81 h->slots = 0;
82 return 1; /* failure */
83 }
84
85 static struct curl_hash_element *
mk_hash_element(const void * key,size_t key_len,const void * p)86 mk_hash_element(const void *key, size_t key_len, const void *p)
87 {
88 /* allocate the struct plus memory after it to store the key */
89 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element) +
90 key_len);
91 if(he) {
92 /* copy the key */
93 memcpy(he->key, key, key_len);
94 he->key_len = key_len;
95 he->ptr = (void *) p;
96 }
97 return he;
98 }
99
100 #define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]
101
102 /* Insert the data in the hash. If there already was a match in the hash,
103 * that data is replaced.
104 *
105 * @unittest: 1305
106 * @unittest: 1602
107 * @unittest: 1603
108 */
109 void *
Curl_hash_add(struct curl_hash * h,void * key,size_t key_len,void * p)110 Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
111 {
112 struct curl_hash_element *he;
113 struct curl_llist_element *le;
114 struct curl_llist *l = FETCH_LIST(h, key, key_len);
115
116 for(le = l->head; le; le = le->next) {
117 he = (struct curl_hash_element *) le->ptr;
118 if(h->comp_func(he->key, he->key_len, key, key_len)) {
119 Curl_llist_remove(l, le, (void *)h);
120 --h->size;
121 break;
122 }
123 }
124
125 he = mk_hash_element(key, key_len, p);
126 if(he) {
127 Curl_llist_insert_next(l, l->tail, he, &he->list);
128 ++h->size;
129 return p; /* return the new entry */
130 }
131
132 return NULL; /* failure */
133 }
134
135 /* Remove the identified hash entry.
136 * Returns non-zero on failure.
137 *
138 * @unittest: 1603
139 */
Curl_hash_delete(struct curl_hash * h,void * key,size_t key_len)140 int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
141 {
142 struct curl_llist_element *le;
143 struct curl_hash_element *he;
144 struct curl_llist *l = FETCH_LIST(h, key, key_len);
145
146 for(le = l->head; le; le = le->next) {
147 he = le->ptr;
148 if(h->comp_func(he->key, he->key_len, key, key_len)) {
149 Curl_llist_remove(l, le, (void *) h);
150 --h->size;
151 return 0;
152 }
153 }
154 return 1;
155 }
156
157 /* Retrieves a hash element.
158 *
159 * @unittest: 1603
160 */
161 void *
Curl_hash_pick(struct curl_hash * h,void * key,size_t key_len)162 Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
163 {
164 struct curl_llist_element *le;
165 struct curl_hash_element *he;
166 struct curl_llist *l;
167
168 if(h) {
169 l = FETCH_LIST(h, key, key_len);
170 for(le = l->head; le; le = le->next) {
171 he = le->ptr;
172 if(h->comp_func(he->key, he->key_len, key, key_len)) {
173 return he->ptr;
174 }
175 }
176 }
177
178 return NULL;
179 }
180
181 #if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
182 void
Curl_hash_apply(curl_hash * h,void * user,void (* cb)(void * user,void * ptr))183 Curl_hash_apply(curl_hash *h, void *user,
184 void (*cb)(void *user, void *ptr))
185 {
186 struct curl_llist_element *le;
187 int i;
188
189 for(i = 0; i < h->slots; ++i) {
190 for(le = (h->table[i])->head;
191 le;
192 le = le->next) {
193 curl_hash_element *el = le->ptr;
194 cb(user, el->ptr);
195 }
196 }
197 }
198 #endif
199
200 /* Destroys all the entries in the given hash and resets its attributes,
201 * prepping the given hash for [static|dynamic] deallocation.
202 *
203 * @unittest: 1305
204 * @unittest: 1602
205 * @unittest: 1603
206 */
207 void
Curl_hash_destroy(struct curl_hash * h)208 Curl_hash_destroy(struct curl_hash *h)
209 {
210 int i;
211
212 for(i = 0; i < h->slots; ++i) {
213 Curl_llist_destroy(&h->table[i], (void *) h);
214 }
215
216 Curl_safefree(h->table);
217 h->size = 0;
218 h->slots = 0;
219 }
220
221 /* Removes all the entries in the given hash.
222 *
223 * @unittest: 1602
224 */
225 void
Curl_hash_clean(struct curl_hash * h)226 Curl_hash_clean(struct curl_hash *h)
227 {
228 Curl_hash_clean_with_criterium(h, NULL, NULL);
229 }
230
231 /* Cleans all entries that pass the comp function criteria. */
232 void
Curl_hash_clean_with_criterium(struct curl_hash * h,void * user,int (* comp)(void *,void *))233 Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
234 int (*comp)(void *, void *))
235 {
236 struct curl_llist_element *le;
237 struct curl_llist_element *lnext;
238 struct curl_llist *list;
239 int i;
240
241 if(!h)
242 return;
243
244 for(i = 0; i < h->slots; ++i) {
245 list = &h->table[i];
246 le = list->head; /* get first list entry */
247 while(le) {
248 struct curl_hash_element *he = le->ptr;
249 lnext = le->next;
250 /* ask the callback function if we shall remove this entry or not */
251 if(comp == NULL || comp(user, he->ptr)) {
252 Curl_llist_remove(list, le, (void *) h);
253 --h->size; /* one less entry in the hash now */
254 }
255 le = lnext;
256 }
257 }
258 }
259
Curl_hash_str(void * key,size_t key_length,size_t slots_num)260 size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
261 {
262 const char *key_str = (const char *) key;
263 const char *end = key_str + key_length;
264 unsigned long h = 5381;
265
266 while(key_str < end) {
267 h += h << 5;
268 h ^= (unsigned long) *key_str++;
269 }
270
271 return (h % slots_num);
272 }
273
Curl_str_key_compare(void * k1,size_t key1_len,void * k2,size_t key2_len)274 size_t Curl_str_key_compare(void *k1, size_t key1_len,
275 void *k2, size_t key2_len)
276 {
277 if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
278 return 1;
279
280 return 0;
281 }
282
Curl_hash_start_iterate(struct curl_hash * hash,struct curl_hash_iterator * iter)283 void Curl_hash_start_iterate(struct curl_hash *hash,
284 struct curl_hash_iterator *iter)
285 {
286 iter->hash = hash;
287 iter->slot_index = 0;
288 iter->current_element = NULL;
289 }
290
291 struct curl_hash_element *
Curl_hash_next_element(struct curl_hash_iterator * iter)292 Curl_hash_next_element(struct curl_hash_iterator *iter)
293 {
294 int i;
295 struct curl_hash *h = iter->hash;
296
297 /* Get the next element in the current list, if any */
298 if(iter->current_element)
299 iter->current_element = iter->current_element->next;
300
301 /* If we have reached the end of the list, find the next one */
302 if(!iter->current_element) {
303 for(i = iter->slot_index; i < h->slots; i++) {
304 if(h->table[i].head) {
305 iter->current_element = h->table[i].head;
306 iter->slot_index = i + 1;
307 break;
308 }
309 }
310 }
311
312 if(iter->current_element) {
313 struct curl_hash_element *he = iter->current_element->ptr;
314 return he;
315 }
316 iter->current_element = NULL;
317 return NULL;
318 }
319
320 #if 0 /* useful function for debugging hashes and their contents */
321 void Curl_hash_print(struct curl_hash *h,
322 void (*func)(void *))
323 {
324 struct curl_hash_iterator iter;
325 struct curl_hash_element *he;
326 int last_index = -1;
327
328 if(!h)
329 return;
330
331 fprintf(stderr, "=Hash dump=\n");
332
333 Curl_hash_start_iterate(h, &iter);
334
335 he = Curl_hash_next_element(&iter);
336 while(he) {
337 if(iter.slot_index != last_index) {
338 fprintf(stderr, "index %d:", iter.slot_index);
339 if(last_index >= 0) {
340 fprintf(stderr, "\n");
341 }
342 last_index = iter.slot_index;
343 }
344
345 if(func)
346 func(he->ptr);
347 else
348 fprintf(stderr, " [%p]", (void *)he->ptr);
349
350 he = Curl_hash_next_element(&iter);
351 }
352 fprintf(stderr, "\n");
353 }
354 #endif
355