1/*************************************************************************** 2 * _ _ ____ _ 3 * Project ___| | | | _ \| | 4 * / __| | | | |_) | | 5 * | (__| |_| | _ <| |___ 6 * \___|\___/|_| \_\_____| 7 * 8 * Copyright (C) 1998 - 2011, Daniel Stenberg, <daniel@haxx.se>, et al. 9 * 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. 13 * 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. 17 * 18 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY 19 * KIND, either express or implied. 20 * 21 ***************************************************************************/ 22 23#include "setup.h" 24 25#include <string.h> 26#include <stdlib.h> 27 28#include "hash.h" 29#include "llist.h" 30 31#define _MPRINTF_REPLACE /* use our functions only */ 32#include <curl/mprintf.h> 33 34#include "curl_memory.h" 35/* The last #include file should be: */ 36#include "memdebug.h" 37 38static void 39hash_element_dtor(void *user, void *element) 40{ 41 struct curl_hash *h = (struct curl_hash *) user; 42 struct curl_hash_element *e = (struct curl_hash_element *) element; 43 44 if(e->key) 45 free(e->key); 46 47 if(e->ptr) 48 h->dtor(e->ptr); 49 50 free(e); 51} 52 53/* return 1 on error, 0 is fine */ 54int 55Curl_hash_init(struct curl_hash *h, 56 int slots, 57 hash_function hfunc, 58 comp_function comparator, 59 curl_hash_dtor dtor) 60{ 61 int i; 62 63 if(!slots || !hfunc || !comparator ||!dtor) { 64 return 1; /* failure */ 65 } 66 67 h->hash_func = hfunc; 68 h->comp_func = comparator; 69 h->dtor = dtor; 70 h->size = 0; 71 h->slots = slots; 72 73 h->table = malloc(slots * sizeof(struct curl_llist *)); 74 if(h->table) { 75 for(i = 0; i < slots; ++i) { 76 h->table[i] = Curl_llist_alloc((curl_llist_dtor) hash_element_dtor); 77 if(!h->table[i]) { 78 while(i--) 79 Curl_llist_destroy(h->table[i], NULL); 80 free(h->table); 81 return 1; /* failure */ 82 } 83 } 84 return 0; /* fine */ 85 } 86 else 87 return 1; /* failure */ 88} 89 90struct curl_hash * 91Curl_hash_alloc(int slots, 92 hash_function hfunc, 93 comp_function comparator, 94 curl_hash_dtor dtor) 95{ 96 struct curl_hash *h; 97 98 if(!slots || !hfunc || !comparator ||!dtor) { 99 return NULL; /* failure */ 100 } 101 102 h = malloc(sizeof(struct curl_hash)); 103 if(h) { 104 if(Curl_hash_init(h, slots, hfunc, comparator, dtor)) { 105 /* failure */ 106 free(h); 107 h = NULL; 108 } 109 } 110 111 return h; 112} 113 114 115 116static struct curl_hash_element * 117mk_hash_element(const void *key, size_t key_len, const void *p) 118{ 119 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element)); 120 121 if(he) { 122 void *dupkey = malloc(key_len); 123 if(dupkey) { 124 /* copy the key */ 125 memcpy(dupkey, key, key_len); 126 127 he->key = dupkey; 128 he->key_len = key_len; 129 he->ptr = (void *) p; 130 } 131 else { 132 /* failed to duplicate the key, free memory and fail */ 133 free(he); 134 he = NULL; 135 } 136 } 137 return he; 138} 139 140#define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)] 141 142/* Insert the data in the hash. If there already was a match in the hash, 143 * that data is replaced. 144 * 145 * @unittest: 1305 146 */ 147void * 148Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p) 149{ 150 struct curl_hash_element *he; 151 struct curl_llist_element *le; 152 struct curl_llist *l = FETCH_LIST (h, key, key_len); 153 154 for(le = l->head; le; le = le->next) { 155 he = (struct curl_hash_element *) le->ptr; 156 if(h->comp_func(he->key, he->key_len, key, key_len)) { 157 Curl_llist_remove(l, le, (void *)h); 158 --h->size; 159 break; 160 } 161 } 162 163 he = mk_hash_element(key, key_len, p); 164 if(he) { 165 if(Curl_llist_insert_next(l, l->tail, he)) { 166 ++h->size; 167 return p; /* return the new entry */ 168 } 169 /* 170 * Couldn't insert it, destroy the 'he' element and the key again. We 171 * don't call hash_element_dtor() since that would also call the 172 * "destructor" for the actual data 'p'. When we fail, we shall not touch 173 * that data. 174 */ 175 free(he->key); 176 free(he); 177 } 178 179 return NULL; /* failure */ 180} 181 182/* remove the identified hash entry, returns non-zero on failure */ 183int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len) 184{ 185 struct curl_llist_element *le; 186 struct curl_hash_element *he; 187 struct curl_llist *l = FETCH_LIST(h, key, key_len); 188 189 for(le = l->head; le; le = le->next) { 190 he = le->ptr; 191 if(h->comp_func(he->key, he->key_len, key, key_len)) { 192 Curl_llist_remove(l, le, (void *) h); 193 return 0; 194 } 195 } 196 return 1; 197} 198 199void * 200Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len) 201{ 202 struct curl_llist_element *le; 203 struct curl_hash_element *he; 204 struct curl_llist *l = FETCH_LIST(h, key, key_len); 205 206 for(le = l->head; le; le = le->next) { 207 he = le->ptr; 208 if(h->comp_func(he->key, he->key_len, key, key_len)) { 209 return he->ptr; 210 } 211 } 212 213 return NULL; 214} 215 216#if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST) 217void 218Curl_hash_apply(curl_hash *h, void *user, 219 void (*cb)(void *user, void *ptr)) 220{ 221 struct curl_llist_element *le; 222 int i; 223 224 for(i = 0; i < h->slots; ++i) { 225 for(le = (h->table[i])->head; 226 le; 227 le = le->next) { 228 curl_hash_element *el = le->ptr; 229 cb(user, el->ptr); 230 } 231 } 232} 233#endif 234 235void 236Curl_hash_clean(struct curl_hash *h) 237{ 238 int i; 239 240 for(i = 0; i < h->slots; ++i) { 241 Curl_llist_destroy(h->table[i], (void *) h); 242 h->table[i] = NULL; 243 } 244 245 free(h->table); 246} 247 248void 249Curl_hash_clean_with_criterium(struct curl_hash *h, void *user, 250 int (*comp)(void *, void *)) 251{ 252 struct curl_llist_element *le; 253 struct curl_llist_element *lnext; 254 struct curl_llist *list; 255 int i; 256 257 for(i = 0; i < h->slots; ++i) { 258 list = h->table[i]; 259 le = list->head; /* get first list entry */ 260 while(le) { 261 struct curl_hash_element *he = le->ptr; 262 lnext = le->next; 263 /* ask the callback function if we shall remove this entry or not */ 264 if(comp(user, he->ptr)) { 265 Curl_llist_remove(list, le, (void *) h); 266 --h->size; /* one less entry in the hash now */ 267 } 268 le = lnext; 269 } 270 } 271} 272 273void 274Curl_hash_destroy(struct curl_hash *h) 275{ 276 if(!h) 277 return; 278 279 Curl_hash_clean(h); 280 281 free(h); 282} 283 284size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num) 285{ 286 const char* key_str = (const char *) key; 287 const char *end = key_str + key_length; 288 unsigned long h = 5381; 289 290 while(key_str < end) { 291 h += h << 5; 292 h ^= (unsigned long) *key_str++; 293 } 294 295 return (h % slots_num); 296} 297 298size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2, size_t key2_len) 299{ 300 char *key1 = (char *)k1; 301 char *key2 = (char *)k2; 302 303 if(key1_len == key2_len && 304 *key1 == *key2 && 305 memcmp(key1, key2, key1_len) == 0) { 306 return 1; 307 } 308 309 return 0; 310} 311 312#if 0 /* useful function for debugging hashes and their contents */ 313void Curl_hash_print(struct curl_hash *h, 314 void (*func)(void *)) 315{ 316 int i; 317 struct curl_llist_element *le; 318 struct curl_llist *list; 319 struct curl_hash_element *he; 320 if(!h) 321 return; 322 323 fprintf(stderr, "=Hash dump=\n"); 324 325 for(i = 0; i < h->slots; i++) { 326 list = h->table[i]; 327 le = list->head; /* get first list entry */ 328 if(le) { 329 fprintf(stderr, "index %d:", i); 330 while(le) { 331 he = le->ptr; 332 if(func) 333 func(he->ptr); 334 else 335 fprintf(stderr, " [%p]", he->ptr); 336 le = le->next; 337 } 338 fprintf(stderr, "\n"); 339 } 340 } 341} 342#endif 343