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