1 /***************************************************************************
3 * Project ___| | | | _ \| |
5 * | (__| |_| | _ <| |___
6 * \___|\___/|_| \_\_____|
8 * Copyright (C) 1998 - 2004, 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 * $Id: hash.c,v 1.20 2004/01/07 09:19:35 bagder Exp $
22 ***************************************************************************/
33 /* this must be the last include file */
39 hash_str(const char *key, size_t key_length)
41 char *end = (char *) key + key_length;
42 unsigned long h = 5381;
46 h ^= (unsigned long) *key++;
53 hash_element_dtor(void *user, void *element)
55 curl_hash *h = (curl_hash *) user;
56 curl_hash_element *e = (curl_hash_element *) element;
67 /* return 1 on error, 0 is fine */
69 Curl_hash_init(curl_hash *h, int slots, curl_hash_dtor dtor)
77 h->table = (curl_llist **) malloc(slots * sizeof(curl_llist *));
79 for (i = 0; i < slots; ++i) {
80 h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
83 Curl_llist_destroy(h->table[i], NULL);
85 return 1; /* failure */
91 return 1; /* failure */
95 Curl_hash_alloc(int slots, curl_hash_dtor dtor)
99 h = (curl_hash *) malloc(sizeof(curl_hash));
101 if(Curl_hash_init(h, slots, dtor)) {
112 hash_key_compare(char *key1, size_t key1_len, char *key2, size_t key2_len)
114 if (key1_len == key2_len &&
116 memcmp(key1, key2, key1_len) == 0) {
123 static curl_hash_element *
124 mk_hash_element(char *key, size_t key_len, const void *p)
126 curl_hash_element *he =
127 (curl_hash_element *) malloc(sizeof(curl_hash_element));
130 he->key = strdup(key);
131 he->key_len = key_len;
132 he->ptr = (void *) p;
137 #define find_slot(__h, __k, __k_len) (hash_str(__k, __k_len) % (__h)->slots)
139 #define FETCH_LIST(x,y,z) x->table[find_slot(x, y, z)]
141 /* Return the data in the hash. If there already was a match in the hash,
142 that data is returned. */
144 Curl_hash_add(curl_hash *h, char *key, size_t key_len, void *p)
146 curl_hash_element *he;
147 curl_llist_element *le;
148 curl_llist *l = FETCH_LIST(h, key, key_len);
150 for (le = l->head; le; le = le->next) {
151 he = (curl_hash_element *) le->ptr;
152 if (hash_key_compare(he->key, he->key_len, key, key_len)) {
153 h->dtor(p); /* remove the NEW entry */
154 return he->ptr; /* return the EXISTING entry */
158 he = mk_hash_element(key, key_len, p);
160 if(Curl_llist_insert_next(l, l->tail, he)) {
162 return p; /* return the new entry */
164 /* couldn't insert it, destroy the 'he' element again */
165 hash_element_dtor(h, he);
167 h->dtor(p); /* remove the NEW entry */
168 return NULL; /* failure */
173 Curl_hash_delete(curl_hash *h, char *key, size_t key_len)
175 curl_hash_element *he;
176 curl_llist_element *le;
177 curl_llist *l = FETCH_LIST(h, key, key_len);
183 if (hash_key_compare(he->key, he->key_len, key, key_len)) {
184 Curl_llist_remove(l, le, (void *) h);
195 Curl_hash_pick(curl_hash *h, char *key, size_t key_len)
197 curl_llist_element *le;
198 curl_hash_element *he;
199 curl_llist *l = FETCH_LIST(h, key, key_len);
205 if (hash_key_compare(he->key, he->key_len, key, key_len)) {
213 #if defined(CURLDEBUG) && defined(AGGRESIVE_TEST)
215 Curl_hash_apply(curl_hash *h, void *user,
216 void (*cb)(void *user, void *ptr))
218 curl_llist_element *le;
221 for (i = 0; i < h->slots; ++i) {
222 for (le = (h->table[i])->head;
225 curl_hash_element *el = le->ptr;
233 Curl_hash_clean(curl_hash *h)
237 for (i = 0; i < h->slots; ++i) {
238 Curl_llist_destroy(h->table[i], (void *) h);
245 Curl_hash_clean_with_criterium(curl_hash *h, void *user,
246 int (*comp)(void *, void *))
248 curl_llist_element *le;
249 curl_llist_element *lnext;
253 for (i = 0; i < h->slots; ++i) {
255 le = list->head; /* get first list entry */
257 curl_hash_element *he = le->ptr;
259 /* ask the callback function if we shall remove this entry or not */
260 if (comp(user, he->ptr)) {
261 Curl_llist_remove(list, le, (void *) h);
262 --h->size; /* one less entry in the hash now */
271 Curl_hash_count(curl_hash *h)
278 Curl_hash_destroy(curl_hash *h)