1 /***************************************************************************
3 * Project ___| | | | _ \| |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
8 * Copyright (C) 1998 - 2020, Daniel Stenberg, <daniel@haxx.se>, et al.
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.
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.
18 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19 * KIND, either express or implied.
21 ***************************************************************************/
23 #include "curl_setup.h"
25 #include <curl/curl.h>
29 #include "curl_memory.h"
31 /* The last #include file should be: */
35 hash_element_dtor(void *user, void *element)
37 struct Curl_hash *h = (struct Curl_hash *) user;
38 struct Curl_hash_element *e = (struct Curl_hash_element *) element;
50 /* Initializes a hash structure.
51 * Return 1 on error, 0 is fine.
57 Curl_hash_init(struct Curl_hash *h,
60 comp_function comparator,
63 if(!slots || !hfunc || !comparator ||!dtor) {
64 return 1; /* failure */
68 h->comp_func = comparator;
73 h->table = malloc(slots * sizeof(struct Curl_llist));
76 for(i = 0; i < slots; ++i)
77 Curl_llist_init(&h->table[i], (Curl_llist_dtor) hash_element_dtor);
81 return 1; /* failure */
84 static struct Curl_hash_element *
85 mk_hash_element(const void *key, size_t key_len, const void *p)
87 /* allocate the struct plus memory after it to store the key */
88 struct Curl_hash_element *he = malloc(sizeof(struct Curl_hash_element) +
92 memcpy(he->key, key, key_len);
93 he->key_len = key_len;
99 #define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]
101 /* Insert the data in the hash. If there already was a match in the hash,
102 * that data is replaced.
109 Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
111 struct Curl_hash_element *he;
112 struct Curl_llist_element *le;
113 struct Curl_llist *l = FETCH_LIST(h, key, key_len);
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);
124 he = mk_hash_element(key, key_len, p);
126 Curl_llist_insert_next(l, l->tail, he, &he->list);
128 return p; /* return the new entry */
131 return NULL; /* failure */
134 /* Remove the identified hash entry.
135 * Returns non-zero on failure.
139 int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
141 struct Curl_llist_element *le;
142 struct Curl_llist *l = FETCH_LIST(h, key, key_len);
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);
155 /* Retrieves a hash element.
160 Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
162 struct Curl_llist_element *le;
163 struct Curl_llist *l;
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)) {
178 #if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
180 Curl_hash_apply(Curl_hash *h, void *user,
181 void (*cb)(void *user, void *ptr))
183 struct Curl_llist_element *le;
186 for(i = 0; i < h->slots; ++i) {
187 for(le = (h->table[i])->head;
190 Curl_hash_element *el = le->ptr;
197 /* Destroys all the entries in the given hash and resets its attributes,
198 * prepping the given hash for [static|dynamic] deallocation.
205 Curl_hash_destroy(struct Curl_hash *h)
209 for(i = 0; i < h->slots; ++i) {
210 Curl_llist_destroy(&h->table[i], (void *) h);
213 Curl_safefree(h->table);
218 /* Removes all the entries in the given hash.
223 Curl_hash_clean(struct Curl_hash *h)
225 Curl_hash_clean_with_criterium(h, NULL, NULL);
228 /* Cleans all entries that pass the comp function criteria. */
230 Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user,
231 int (*comp)(void *, void *))
233 struct Curl_llist_element *le;
234 struct Curl_llist_element *lnext;
235 struct Curl_llist *list;
241 for(i = 0; i < h->slots; ++i) {
243 le = list->head; /* get first list entry */
245 struct Curl_hash_element *he = le->ptr;
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 */
257 size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
259 const char *key_str = (const char *) key;
260 const char *end = key_str + key_length;
263 while(key_str < end) {
268 return (h % slots_num);
271 size_t Curl_str_key_compare(void *k1, size_t key1_len,
272 void *k2, size_t key2_len)
274 if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
280 void Curl_hash_start_iterate(struct Curl_hash *hash,
281 struct Curl_hash_iterator *iter)
284 iter->slot_index = 0;
285 iter->current_element = NULL;
288 struct Curl_hash_element *
289 Curl_hash_next_element(struct Curl_hash_iterator *iter)
291 struct Curl_hash *h = iter->hash;
293 /* Get the next element in the current list, if any */
294 if(iter->current_element)
295 iter->current_element = iter->current_element->next;
297 /* If we have reached the end of the list, find the next one */
298 if(!iter->current_element) {
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;
309 if(iter->current_element) {
310 struct Curl_hash_element *he = iter->current_element->ptr;
313 iter->current_element = NULL;
317 #if 0 /* useful function for debugging hashes and their contents */
318 void Curl_hash_print(struct Curl_hash *h,
319 void (*func)(void *))
321 struct Curl_hash_iterator iter;
322 struct Curl_hash_element *he;
328 fprintf(stderr, "=Hash dump=\n");
330 Curl_hash_start_iterate(h, &iter);
332 he = Curl_hash_next_element(&iter);
334 if(iter.slot_index != last_index) {
335 fprintf(stderr, "index %d:", iter.slot_index);
336 if(last_index >= 0) {
337 fprintf(stderr, "\n");
339 last_index = iter.slot_index;
345 fprintf(stderr, " [%p]", (void *)he->ptr);
347 he = Curl_hash_next_element(&iter);
349 fprintf(stderr, "\n");