1/***************************************************************************
2 * _ _ ____ _
3 * Project ___| | | | _ \| |
4 * / __| | | | |_) | |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
7 *
8 * Copyright (C) 1998 - 2021, 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 ***************************************************************************/
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
34static void
35hash_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 */
56int
57Curl_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
84static struct Curl_hash_element *
85mk_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 */
108void *
109Curl_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 */
139int 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 */
159void *
160Curl_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(AGGRESSIVE_TEST)
179void
180Curl_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 */
204void
205Curl_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 */
222void
223Curl_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. */
229void
230Curl_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 || 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
257size_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
271size_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
280void 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
288struct Curl_hash_element *
289Curl_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 */
318void 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