1 /***************************************************************************
3 * Project ___| | | | _ \| |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
8 * Copyright (C) 1998 - 2008, 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 http://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.
22 ***************************************************************************/
33 /* this must be the last include file */
37 hash_element_dtor(void *user, void *element)
39 struct curl_hash *h = (struct curl_hash *) user;
40 struct curl_hash_element *e = (struct curl_hash_element *) element;
50 /* return 1 on error, 0 is fine */
52 Curl_hash_init(struct curl_hash *h,
55 comp_function comparator,
60 if(!slots || !hfunc || !comparator ||!dtor) {
61 return 1; /* failure */
65 h->comp_func = comparator;
70 h->table = malloc(slots * sizeof(struct curl_llist *));
72 for (i = 0; i < slots; ++i) {
73 h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
76 Curl_llist_destroy(h->table[i], NULL);
78 return 1; /* failure */
84 return 1; /* failure */
88 Curl_hash_alloc(int slots,
90 comp_function comparator,
95 if(!slots || !hfunc || !comparator ||!dtor) {
96 return NULL; /* failure */
99 h = malloc(sizeof(struct curl_hash));
101 if(Curl_hash_init(h, slots, hfunc, comparator, dtor)) {
113 static struct curl_hash_element *
114 mk_hash_element(const void *key, size_t key_len, const void *p)
116 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element));
119 void *dupkey = malloc(key_len);
122 memcpy(dupkey, key, key_len);
125 he->key_len = key_len;
126 he->ptr = (void *) p;
129 /* failed to duplicate the key, free memory and fail */
137 #define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)]
139 /* Return the data in the hash. If there already was a match in the hash,
140 that data is returned. */
142 Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
144 struct curl_hash_element *he;
145 struct curl_llist_element *le;
146 struct curl_llist *l = FETCH_LIST (h, key, key_len);
148 for (le = l->head; le; le = le->next) {
149 he = (struct curl_hash_element *) le->ptr;
150 if(h->comp_func(he->key, he->key_len, key, key_len)) {
151 h->dtor(p); /* remove the NEW entry */
152 return he->ptr; /* return the EXISTING entry */
156 he = mk_hash_element(key, key_len, p);
158 if(Curl_llist_insert_next(l, l->tail, he)) {
160 return p; /* return the new entry */
163 * Couldn't insert it, destroy the 'he' element and the key again. We
164 * don't call hash_element_dtor() since that would also call the
165 * "destructor" for the actual data 'p'. When we fail, we shall not touch
172 return NULL; /* failure */
175 /* remove the identified hash entry, returns non-zero on failure */
176 int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
178 struct curl_llist_element *le;
179 struct curl_hash_element *he;
180 struct curl_llist *l = FETCH_LIST(h, key, key_len);
182 for (le = l->head; le; le = le->next) {
184 if(h->comp_func(he->key, he->key_len, key, key_len)) {
185 Curl_llist_remove(l, le, (void *) h);
193 Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
195 struct curl_llist_element *le;
196 struct curl_hash_element *he;
197 struct curl_llist *l = FETCH_LIST(h, key, key_len);
199 for (le = l->head; le; le = le->next) {
201 if(h->comp_func(he->key, he->key_len, key, key_len)) {
209 #if defined(CURLDEBUG) && defined(AGGRESIVE_TEST)
211 Curl_hash_apply(curl_hash *h, void *user,
212 void (*cb)(void *user, void *ptr))
214 struct curl_llist_element *le;
217 for (i = 0; i < h->slots; ++i) {
218 for (le = (h->table[i])->head;
221 curl_hash_element *el = le->ptr;
229 Curl_hash_clean(struct curl_hash *h)
233 for (i = 0; i < h->slots; ++i) {
234 Curl_llist_destroy(h->table[i], (void *) h);
242 Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
243 int (*comp)(void *, void *))
245 struct curl_llist_element *le;
246 struct curl_llist_element *lnext;
247 struct curl_llist *list;
250 for (i = 0; i < h->slots; ++i) {
252 le = list->head; /* get first list entry */
254 struct curl_hash_element *he = le->ptr;
256 /* ask the callback function if we shall remove this entry or not */
257 if(comp(user, he->ptr)) {
258 Curl_llist_remove(list, le, (void *) h);
259 --h->size; /* one less entry in the hash now */
267 Curl_hash_destroy(struct curl_hash *h)
277 size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num)
279 const char* key_str = (const char *) key;
280 const char *end = key_str + key_length;
281 unsigned long h = 5381;
283 while(key_str < end) {
285 h ^= (unsigned long) *key_str++;
288 return (h % slots_num);
291 size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2, size_t key2_len)
293 char *key1 = (char *)k1;
294 char *key2 = (char *)k2;
296 if(key1_len == key2_len &&
298 memcmp(key1, key2, key1_len) == 0) {
305 #if 0 /* useful function for debugging hashes and their contents */
306 void Curl_hash_print(struct curl_hash *h,
307 void (*func)(void *))
310 struct curl_llist_element *le;
311 struct curl_llist *list;
312 struct curl_hash_element *he;
316 fprintf(stderr, "=Hash dump=\n");
318 for (i = 0; i < h->slots; i++) {
320 le = list->head; /* get first list entry */
322 fprintf(stderr, "index %d:", i);
328 fprintf(stderr, " [%p]", he->ptr);
331 fprintf(stderr, "\n");