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
36static void
37hash_element_dtor(void *user, void *element)
38{
39 struct Curl_hash *h = (struct Curl_hash *) user;
40 struct Curl_hash_element *e = (struct Curl_hash_element *) element;
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 */
58void
59Curl_hash_init(struct Curl_hash *h,
60 int slots,
61 hash_function hfunc,
62 comp_function comparator,
63 Curl_hash_dtor dtor)
64{
65 DEBUGASSERT(h);
66 DEBUGASSERT(slots);
67 DEBUGASSERT(hfunc);
68 DEBUGASSERT(comparator);
69 DEBUGASSERT(dtor);
70
71 h->table = NULL;
72 h->hash_func = hfunc;
73 h->comp_func = comparator;
74 h->dtor = dtor;
75 h->size = 0;
76 h->slots = slots;
77}
78
79static struct Curl_hash_element *
80mk_hash_element(const void *key, size_t key_len, const void *p)
81{
82 /* allocate the struct plus memory after it to store the key */
83 struct Curl_hash_element *he = malloc(sizeof(struct Curl_hash_element) +
84 key_len);
85 if(he) {
86 /* copy the key */
87 memcpy(dest: he->key, src: key, n: key_len);
88 he->key_len = key_len;
89 he->ptr = (void *) p;
90 }
91 return he;
92}
93
94#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 */
104void *
105Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
106{
107 struct Curl_hash_element *he;
108 struct Curl_llist_element *le;
109 struct Curl_llist *l;
110
111 DEBUGASSERT(h);
112 DEBUGASSERT(h->slots);
113 if(!h->table) {
114 int i;
115 h->table = malloc(h->slots * sizeof(struct Curl_llist));
116 if(!h->table)
117 return NULL; /* OOM */
118 for(i = 0; i < h->slots; ++i)
119 Curl_llist_init(&h->table[i], hash_element_dtor);
120 }
121
122 l = FETCH_LIST(h, key, key_len);
123
124 for(le = l->head; le; le = le->next) {
125 he = (struct Curl_hash_element *) le->ptr;
126 if(h->comp_func(he->key, he->key_len, key, key_len)) {
127 Curl_llist_remove(l, le, (void *)h);
128 --h->size;
129 break;
130 }
131 }
132
133 he = mk_hash_element(key, key_len, p);
134 if(he) {
135 Curl_llist_insert_next(l, l->tail, he, node: &he->list);
136 ++h->size;
137 return p; /* return the new entry */
138 }
139
140 return NULL; /* failure */
141}
142
143/* Remove the identified hash entry.
144 * Returns non-zero on failure.
145 *
146 * @unittest: 1603
147 */
148int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
149{
150 struct Curl_llist_element *le;
151 struct Curl_llist *l;
152
153 DEBUGASSERT(h);
154 DEBUGASSERT(h->slots);
155 if(h->table) {
156 l = FETCH_LIST(h, key, key_len);
157
158 for(le = l->head; le; le = le->next) {
159 struct Curl_hash_element *he = le->ptr;
160 if(h->comp_func(he->key, he->key_len, key, key_len)) {
161 Curl_llist_remove(l, le, (void *) h);
162 --h->size;
163 return 0;
164 }
165 }
166 }
167 return 1;
168}
169
170/* Retrieves a hash element.
171 *
172 * @unittest: 1603
173 */
174void *
175Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
176{
177 struct Curl_llist_element *le;
178 struct Curl_llist *l;
179
180 DEBUGASSERT(h);
181 if(h->table) {
182 DEBUGASSERT(h->slots);
183 l = FETCH_LIST(h, key, key_len);
184 for(le = l->head; le; le = le->next) {
185 struct Curl_hash_element *he = le->ptr;
186 if(h->comp_func(he->key, he->key_len, key, key_len)) {
187 return he->ptr;
188 }
189 }
190 }
191
192 return NULL;
193}
194
195#if defined(DEBUGBUILD) && defined(AGGRESSIVE_TEST)
196void
197Curl_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 */
221void
222Curl_hash_destroy(struct Curl_hash *h)
223{
224 if(h->table) {
225 int i;
226 for(i = 0; i < h->slots; ++i) {
227 Curl_llist_destroy(&h->table[i], (void *) h);
228 }
229 Curl_safefree(h->table);
230 }
231 h->size = 0;
232 h->slots = 0;
233}
234
235/* Removes all the entries in the given hash.
236 *
237 * @unittest: 1602
238 */
239void
240Curl_hash_clean(struct Curl_hash *h)
241{
242 Curl_hash_clean_with_criterium(h, NULL, NULL);
243}
244
245/* Cleans all entries that pass the comp function criteria. */
246void
247Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user,
248 int (*comp)(void *, void *))
249{
250 struct Curl_llist_element *le;
251 struct Curl_llist_element *lnext;
252 struct Curl_llist *list;
253 int i;
254
255 if(!h || !h->table)
256 return;
257
258 for(i = 0; i < h->slots; ++i) {
259 list = &h->table[i];
260 le = list->head; /* get first list entry */
261 while(le) {
262 struct Curl_hash_element *he = le->ptr;
263 lnext = le->next;
264 /* ask the callback function if we shall remove this entry or not */
265 if(!comp || comp(user, he->ptr)) {
266 Curl_llist_remove(list, le, (void *) h);
267 --h->size; /* one less entry in the hash now */
268 }
269 le = lnext;
270 }
271 }
272}
273
274size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
275{
276 const char *key_str = (const char *) key;
277 const char *end = key_str + key_length;
278 size_t h = 5381;
279
280 while(key_str < end) {
281 h += h << 5;
282 h ^= *key_str++;
283 }
284
285 return (h % slots_num);
286}
287
288size_t Curl_str_key_compare(void *k1, size_t key1_len,
289 void *k2, size_t key2_len)
290{
291 if((key1_len == key2_len) && !memcmp(s1: k1, s2: k2, n: key1_len))
292 return 1;
293
294 return 0;
295}
296
297void Curl_hash_start_iterate(struct Curl_hash *hash,
298 struct Curl_hash_iterator *iter)
299{
300 iter->hash = hash;
301 iter->slot_index = 0;
302 iter->current_element = NULL;
303}
304
305struct Curl_hash_element *
306Curl_hash_next_element(struct Curl_hash_iterator *iter)
307{
308 struct Curl_hash *h = iter->hash;
309
310 if(!h->table)
311 return NULL; /* empty hash, nothing to return */
312
313 /* Get the next element in the current list, if any */
314 if(iter->current_element)
315 iter->current_element = iter->current_element->next;
316
317 /* If we have reached the end of the list, find the next one */
318 if(!iter->current_element) {
319 int i;
320 for(i = iter->slot_index; i < h->slots; i++) {
321 if(h->table[i].head) {
322 iter->current_element = h->table[i].head;
323 iter->slot_index = i + 1;
324 break;
325 }
326 }
327 }
328
329 if(iter->current_element) {
330 struct Curl_hash_element *he = iter->current_element->ptr;
331 return he;
332 }
333 return NULL;
334}
335
336#if 0 /* useful function for debugging hashes and their contents */
337void Curl_hash_print(struct Curl_hash *h,
338 void (*func)(void *))
339{
340 struct Curl_hash_iterator iter;
341 struct Curl_hash_element *he;
342 int last_index = -1;
343
344 if(!h)
345 return;
346
347 fprintf(stderr, "=Hash dump=\n");
348
349 Curl_hash_start_iterate(h, &iter);
350
351 he = Curl_hash_next_element(&iter);
352 while(he) {
353 if(iter.slot_index != last_index) {
354 fprintf(stderr, "index %d:", iter.slot_index);
355 if(last_index >= 0) {
356 fprintf(stderr, "\n");
357 }
358 last_index = iter.slot_index;
359 }
360
361 if(func)
362 func(he->ptr);
363 else
364 fprintf(stderr, " [%p]", (void *)he->ptr);
365
366 he = Curl_hash_next_element(&iter);
367 }
368 fprintf(stderr, "\n");
369}
370#endif
371