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