1 | /*************************************************************************** |
2 | * _ _ ____ _ |
3 | * Project ___| | | | _ \| | |
4 | * / __| | | | |_) | | |
5 | * | (__| |_| | _ <| |___ |
6 | * \___|\___/|_| \_\_____| |
7 | * |
8 | * Copyright (C) 1998 - 2018, 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 |
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 |
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 * |
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 * |
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 | */ |
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 * |
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 |
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 |
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 |
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 |
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 | |
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 | |
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 | |
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 * |
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 | |