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