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