1 /***************************************************************************
3 * Project ___| | | | _ \| |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
8 * Copyright (C) 1998 - 2009, 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 ***************************************************************************/
32 #define _MPRINTF_REPLACE /* use our functions only */
33 #include <curl/mprintf.h>
35 #include "curl_memory.h"
36 /* The last #include file should be: */
40 hash_element_dtor(void *user, void *element)
42 struct curl_hash *h = (struct curl_hash *) user;
43 struct curl_hash_element *e = (struct curl_hash_element *) element;
54 /* return 1 on error, 0 is fine */
56 Curl_hash_init(struct curl_hash *h,
59 comp_function comparator,
64 if(!slots || !hfunc || !comparator ||!dtor) {
65 return 1; /* failure */
69 h->comp_func = comparator;
74 h->table = malloc(slots * sizeof(struct curl_llist *));
76 for (i = 0; i < slots; ++i) {
77 h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
80 Curl_llist_destroy(h->table[i], NULL);
82 return 1; /* failure */
88 return 1; /* failure */
92 Curl_hash_alloc(int slots,
94 comp_function comparator,
99 if(!slots || !hfunc || !comparator ||!dtor) {
100 return NULL; /* failure */
103 h = malloc(sizeof(struct curl_hash));
105 if(Curl_hash_init(h, slots, hfunc, comparator, dtor)) {
117 static struct curl_hash_element *
118 mk_hash_element(const void *key, size_t key_len, const void *p)
120 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element));
123 void *dupkey = malloc(key_len);
126 memcpy(dupkey, key, key_len);
129 he->key_len = key_len;
130 he->ptr = (void *) p;
133 /* failed to duplicate the key, free memory and fail */
141 #define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)]
143 /* Insert the data in the hash. If there already was a match in the hash,
144 that data is replaced. */
146 Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
148 struct curl_hash_element *he;
149 struct curl_llist_element *le;
150 struct curl_llist *l = FETCH_LIST (h, key, key_len);
152 for (le = l->head; le; le = le->next) {
153 he = (struct curl_hash_element *) le->ptr;
154 if(h->comp_func(he->key, he->key_len, key, key_len)) {
155 Curl_llist_remove(l, le, (void *)h);
161 he = mk_hash_element(key, key_len, p);
163 if(Curl_llist_insert_next(l, l->tail, he)) {
165 return p; /* return the new entry */
168 * Couldn't insert it, destroy the 'he' element and the key again. We
169 * don't call hash_element_dtor() since that would also call the
170 * "destructor" for the actual data 'p'. When we fail, we shall not touch
177 return NULL; /* failure */
180 /* remove the identified hash entry, returns non-zero on failure */
181 int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
183 struct curl_llist_element *le;
184 struct curl_hash_element *he;
185 struct curl_llist *l = FETCH_LIST(h, key, key_len);
187 for (le = l->head; le; le = le->next) {
189 if(h->comp_func(he->key, he->key_len, key, key_len)) {
190 Curl_llist_remove(l, le, (void *) h);
198 Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
200 struct curl_llist_element *le;
201 struct curl_hash_element *he;
202 struct curl_llist *l = FETCH_LIST(h, key, key_len);
204 for (le = l->head; le; le = le->next) {
206 if(h->comp_func(he->key, he->key_len, key, key_len)) {
214 #if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
216 Curl_hash_apply(curl_hash *h, void *user,
217 void (*cb)(void *user, void *ptr))
219 struct curl_llist_element *le;
222 for (i = 0; i < h->slots; ++i) {
223 for (le = (h->table[i])->head;
226 curl_hash_element *el = le->ptr;
234 Curl_hash_clean(struct curl_hash *h)
238 for (i = 0; i < h->slots; ++i) {
239 Curl_llist_destroy(h->table[i], (void *) h);
247 Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
248 int (*comp)(void *, void *))
250 struct curl_llist_element *le;
251 struct curl_llist_element *lnext;
252 struct curl_llist *list;
255 for (i = 0; i < h->slots; ++i) {
257 le = list->head; /* get first list entry */
259 struct curl_hash_element *he = le->ptr;
261 /* ask the callback function if we shall remove this entry or not */
262 if(comp(user, he->ptr)) {
263 Curl_llist_remove(list, le, (void *) h);
264 --h->size; /* one less entry in the hash now */
272 Curl_hash_destroy(struct curl_hash *h)
282 size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num)
284 const char* key_str = (const char *) key;
285 const char *end = key_str + key_length;
286 unsigned long h = 5381;
288 while(key_str < end) {
290 h ^= (unsigned long) *key_str++;
293 return (h % slots_num);
296 size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2, size_t key2_len)
298 char *key1 = (char *)k1;
299 char *key2 = (char *)k2;
301 if(key1_len == key2_len &&
303 memcmp(key1, key2, key1_len) == 0) {
310 #if 0 /* useful function for debugging hashes and their contents */
311 void Curl_hash_print(struct curl_hash *h,
312 void (*func)(void *))
315 struct curl_llist_element *le;
316 struct curl_llist *list;
317 struct curl_hash_element *he;
321 fprintf(stderr, "=Hash dump=\n");
323 for (i = 0; i < h->slots; i++) {
325 le = list->head; /* get first list entry */
327 fprintf(stderr, "index %d:", i);
333 fprintf(stderr, " [%p]", he->ptr);
336 fprintf(stderr, "\n");