1 /***************************************************************************
3 * Project ___| | | | _ \| |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
8 * Copyright (C) 1998 - 2013, 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.
21 ***************************************************************************/
23 #include "curl_setup.h"
28 #define _MPRINTF_REPLACE /* use our functions only */
29 #include <curl/mprintf.h>
31 #include "curl_memory.h"
32 /* The last #include file should be: */
36 hash_element_dtor(void *user, void *element)
38 struct curl_hash *h = (struct curl_hash *) user;
39 struct curl_hash_element *e = (struct curl_hash_element *) element;
41 Curl_safefree(e->key);
53 /* return 1 on error, 0 is fine */
55 Curl_hash_init(struct curl_hash *h,
58 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 *));
75 for(i = 0; i < slots; ++i) {
76 h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
79 Curl_llist_destroy(h->table[i], NULL);
85 return 1; /* failure */
92 return 1; /* failure */
97 Curl_hash_alloc(int slots,
99 comp_function comparator,
104 if(!slots || !hfunc || !comparator ||!dtor) {
105 return NULL; /* failure */
108 h = malloc(sizeof(struct curl_hash));
110 if(Curl_hash_init(h, slots, hfunc, comparator, dtor)) {
122 static struct curl_hash_element *
123 mk_hash_element(const void *key, size_t key_len, const void *p)
125 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element));
128 void *dupkey = malloc(key_len);
131 memcpy(dupkey, key, key_len);
134 he->key_len = key_len;
135 he->ptr = (void *) p;
138 /* failed to duplicate the key, free memory and fail */
146 #define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)]
148 /* Insert the data in the hash. If there already was a match in the hash,
149 * that data is replaced.
154 Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
156 struct curl_hash_element *he;
157 struct curl_llist_element *le;
158 struct curl_llist *l = FETCH_LIST (h, key, key_len);
160 for(le = l->head; le; le = le->next) {
161 he = (struct curl_hash_element *) le->ptr;
162 if(h->comp_func(he->key, he->key_len, key, key_len)) {
163 Curl_llist_remove(l, le, (void *)h);
169 he = mk_hash_element(key, key_len, p);
171 if(Curl_llist_insert_next(l, l->tail, he)) {
173 return p; /* return the new entry */
176 * Couldn't insert it, destroy the 'he' element and the key again. We
177 * don't call hash_element_dtor() since that would also call the
178 * "destructor" for the actual data 'p'. When we fail, we shall not touch
185 return NULL; /* failure */
188 /* remove the identified hash entry, returns non-zero on failure */
189 int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
191 struct curl_llist_element *le;
192 struct curl_hash_element *he;
193 struct curl_llist *l = FETCH_LIST(h, key, key_len);
195 for(le = l->head; le; le = le->next) {
197 if(h->comp_func(he->key, he->key_len, key, key_len)) {
198 Curl_llist_remove(l, le, (void *) h);
207 Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
209 struct curl_llist_element *le;
210 struct curl_hash_element *he;
211 struct curl_llist *l;
214 l = FETCH_LIST(h, key, key_len);
215 for(le = l->head; le; le = le->next) {
217 if(h->comp_func(he->key, he->key_len, key, key_len)) {
226 #if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
228 Curl_hash_apply(curl_hash *h, void *user,
229 void (*cb)(void *user, void *ptr))
231 struct curl_llist_element *le;
234 for(i = 0; i < h->slots; ++i) {
235 for(le = (h->table[i])->head;
238 curl_hash_element *el = le->ptr;
246 Curl_hash_clean(struct curl_hash *h)
250 for(i = 0; i < h->slots; ++i) {
251 Curl_llist_destroy(h->table[i], (void *) h);
255 Curl_safefree(h->table);
261 Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
262 int (*comp)(void *, void *))
264 struct curl_llist_element *le;
265 struct curl_llist_element *lnext;
266 struct curl_llist *list;
272 for(i = 0; i < h->slots; ++i) {
274 le = list->head; /* get first list entry */
276 struct curl_hash_element *he = le->ptr;
278 /* ask the callback function if we shall remove this entry or not */
279 if(comp(user, he->ptr)) {
280 Curl_llist_remove(list, le, (void *) h);
281 --h->size; /* one less entry in the hash now */
289 Curl_hash_destroy(struct curl_hash *h)
299 size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num)
301 const char* key_str = (const char *) key;
302 const char *end = key_str + key_length;
303 unsigned long h = 5381;
305 while(key_str < end) {
307 h ^= (unsigned long) *key_str++;
310 return (h % slots_num);
313 size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2, size_t key2_len)
315 char *key1 = (char *)k1;
316 char *key2 = (char *)k2;
318 if(key1_len == key2_len &&
320 memcmp(key1, key2, key1_len) == 0) {
327 void Curl_hash_start_iterate(struct curl_hash *hash,
328 struct curl_hash_iterator *iter)
331 iter->slot_index = 0;
332 iter->current_element = NULL;
335 struct curl_hash_element *
336 Curl_hash_next_element(struct curl_hash_iterator *iter)
339 struct curl_hash *h = iter->hash;
341 /* Get the next element in the current list, if any */
342 if(iter->current_element)
343 iter->current_element = iter->current_element->next;
345 /* If we have reached the end of the list, find the next one */
346 if(!iter->current_element) {
347 for(i = iter->slot_index;i < h->slots;i++) {
348 if(h->table[i]->head) {
349 iter->current_element = h->table[i]->head;
350 iter->slot_index = i+1;
356 if(iter->current_element) {
357 struct curl_hash_element *he = iter->current_element->ptr;
361 iter->current_element = NULL;
366 #if 0 /* useful function for debugging hashes and their contents */
367 void Curl_hash_print(struct curl_hash *h,
368 void (*func)(void *))
370 struct curl_hash_iterator iter;
371 struct curl_hash_element *he;
377 fprintf(stderr, "=Hash dump=\n");
379 Curl_hash_start_iterate(h, &iter);
381 he = Curl_hash_next_element(&iter);
383 if(iter.slot_index != last_index) {
384 fprintf(stderr, "index %d:", iter.slot_index);
385 if(last_index >= 0) {
386 fprintf(stderr, "\n");
388 last_index = iter.slot_index;
394 fprintf(stderr, " [%p]", (void *)he->ptr);
396 he = Curl_hash_next_element(&iter);
398 fprintf(stderr, "\n");