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