1/*************************************************************************** 2 * _ _ ____ _ 3 * Project ___| | | | _ \| | 4 * / __| | | | |_) | | 5 * | (__| |_| | _ <| |___ 6 * \___|\___/|_| \_\_____| 7 * 8 * Copyright (C) 1998 - 2013, 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 "curl_setup.h" 24 25#include "hash.h" 26#include "llist.h" 27 28#define _MPRINTF_REPLACE /* use our functions only */ 29#include <curl/mprintf.h> 30 31#include "curl_memory.h" 32/* The last #include file should be: */ 33#include "memdebug.h" 34 35static void 36hash_element_dtor(void *user, void *element) 37{ 38 struct curl_hash *h = (struct curl_hash *) user; 39 struct curl_hash_element *e = (struct curl_hash_element *) element; 40 41 Curl_safefree(e->key); 42 43 if(e->ptr) { 44 h->dtor(e->ptr); 45 e->ptr = NULL; 46 } 47 48 e->key_len = 0; 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 h->table[i] = NULL; 81 } 82 free(h->table); 83 h->table = NULL; 84 h->slots = 0; 85 return 1; /* failure */ 86 } 87 } 88 return 0; /* fine */ 89 } 90 else { 91 h->slots = 0; 92 return 1; /* failure */ 93 } 94} 95 96struct curl_hash * 97Curl_hash_alloc(int slots, 98 hash_function hfunc, 99 comp_function comparator, 100 curl_hash_dtor dtor) 101{ 102 struct curl_hash *h; 103 104 if(!slots || !hfunc || !comparator ||!dtor) { 105 return NULL; /* failure */ 106 } 107 108 h = malloc(sizeof(struct curl_hash)); 109 if(h) { 110 if(Curl_hash_init(h, slots, hfunc, comparator, dtor)) { 111 /* failure */ 112 free(h); 113 h = NULL; 114 } 115 } 116 117 return h; 118} 119 120 121 122static struct curl_hash_element * 123mk_hash_element(const void *key, size_t key_len, const void *p) 124{ 125 struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element)); 126 127 if(he) { 128 void *dupkey = malloc(key_len); 129 if(dupkey) { 130 /* copy the key */ 131 memcpy(dupkey, key, key_len); 132 133 he->key = dupkey; 134 he->key_len = key_len; 135 he->ptr = (void *) p; 136 } 137 else { 138 /* failed to duplicate the key, free memory and fail */ 139 free(he); 140 he = NULL; 141 } 142 } 143 return he; 144} 145 146#define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)] 147 148/* Insert the data in the hash. If there already was a match in the hash, 149 * that data is replaced. 150 * 151 * @unittest: 1305 152 */ 153void * 154Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p) 155{ 156 struct curl_hash_element *he; 157 struct curl_llist_element *le; 158 struct curl_llist *l = FETCH_LIST (h, key, key_len); 159 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); 164 --h->size; 165 break; 166 } 167 } 168 169 he = mk_hash_element(key, key_len, p); 170 if(he) { 171 if(Curl_llist_insert_next(l, l->tail, he)) { 172 ++h->size; 173 return p; /* return the new entry */ 174 } 175 /* 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 179 * that data. 180 */ 181 free(he->key); 182 free(he); 183 } 184 185 return NULL; /* failure */ 186} 187 188/* remove the identified hash entry, returns non-zero on failure */ 189int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len) 190{ 191 struct curl_llist_element *le; 192 struct curl_hash_element *he; 193 struct curl_llist *l = FETCH_LIST(h, key, key_len); 194 195 for(le = l->head; le; le = le->next) { 196 he = le->ptr; 197 if(h->comp_func(he->key, he->key_len, key, key_len)) { 198 Curl_llist_remove(l, le, (void *) h); 199 --h->size; 200 return 0; 201 } 202 } 203 return 1; 204} 205 206void * 207Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len) 208{ 209 struct curl_llist_element *le; 210 struct curl_hash_element *he; 211 struct curl_llist *l; 212 213 if(h) { 214 l = FETCH_LIST(h, key, key_len); 215 for(le = l->head; le; le = le->next) { 216 he = le->ptr; 217 if(h->comp_func(he->key, he->key_len, key, key_len)) { 218 return he->ptr; 219 } 220 } 221 } 222 223 return NULL; 224} 225 226#if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST) 227void 228Curl_hash_apply(curl_hash *h, void *user, 229 void (*cb)(void *user, void *ptr)) 230{ 231 struct curl_llist_element *le; 232 int i; 233 234 for(i = 0; i < h->slots; ++i) { 235 for(le = (h->table[i])->head; 236 le; 237 le = le->next) { 238 curl_hash_element *el = le->ptr; 239 cb(user, el->ptr); 240 } 241 } 242} 243#endif 244 245void 246Curl_hash_clean(struct curl_hash *h) 247{ 248 int i; 249 250 for(i = 0; i < h->slots; ++i) { 251 Curl_llist_destroy(h->table[i], (void *) h); 252 h->table[i] = NULL; 253 } 254 255 Curl_safefree(h->table); 256 h->size = 0; 257 h->slots = 0; 258} 259 260void 261Curl_hash_clean_with_criterium(struct curl_hash *h, void *user, 262 int (*comp)(void *, void *)) 263{ 264 struct curl_llist_element *le; 265 struct curl_llist_element *lnext; 266 struct curl_llist *list; 267 int i; 268 269 if(!h) 270 return; 271 272 for(i = 0; i < h->slots; ++i) { 273 list = h->table[i]; 274 le = list->head; /* get first list entry */ 275 while(le) { 276 struct curl_hash_element *he = le->ptr; 277 lnext = le->next; 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 */ 282 } 283 le = lnext; 284 } 285 } 286} 287 288void 289Curl_hash_destroy(struct curl_hash *h) 290{ 291 if(!h) 292 return; 293 294 Curl_hash_clean(h); 295 296 free(h); 297} 298 299size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num) 300{ 301 const char* key_str = (const char *) key; 302 const char *end = key_str + key_length; 303 unsigned long h = 5381; 304 305 while(key_str < end) { 306 h += h << 5; 307 h ^= (unsigned long) *key_str++; 308 } 309 310 return (h % slots_num); 311} 312 313size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2, size_t key2_len) 314{ 315 char *key1 = (char *)k1; 316 char *key2 = (char *)k2; 317 318 if(key1_len == key2_len && 319 *key1 == *key2 && 320 memcmp(key1, key2, key1_len) == 0) { 321 return 1; 322 } 323 324 return 0; 325} 326 327void Curl_hash_start_iterate(struct curl_hash *hash, 328 struct curl_hash_iterator *iter) 329{ 330 iter->hash = hash; 331 iter->slot_index = 0; 332 iter->current_element = NULL; 333} 334 335struct curl_hash_element * 336Curl_hash_next_element(struct curl_hash_iterator *iter) 337{ 338 int i; 339 struct curl_hash *h = iter->hash; 340 341 /* Get the next element in the current list, if any */ 342 if(iter->current_element) 343 iter->current_element = iter->current_element->next; 344 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; 351 break; 352 } 353 } 354 } 355 356 if(iter->current_element) { 357 struct curl_hash_element *he = iter->current_element->ptr; 358 return he; 359 } 360 else { 361 iter->current_element = NULL; 362 return NULL; 363 } 364} 365 366#if 0 /* useful function for debugging hashes and their contents */ 367void Curl_hash_print(struct curl_hash *h, 368 void (*func)(void *)) 369{ 370 struct curl_hash_iterator iter; 371 struct curl_hash_element *he; 372 int last_index = -1; 373 374 if(!h) 375 return; 376 377 fprintf(stderr, "=Hash dump=\n"); 378 379 Curl_hash_start_iterate(h, &iter); 380 381 he = Curl_hash_next_element(&iter); 382 while(he) { 383 if(iter.slot_index != last_index) { 384 fprintf(stderr, "index %d:", iter.slot_index); 385 if(last_index >= 0) { 386 fprintf(stderr, "\n"); 387 } 388 last_index = iter.slot_index; 389 } 390 391 if(func) 392 func(he->ptr); 393 else 394 fprintf(stderr, " [%p]", (void *)he->ptr); 395 396 he = Curl_hash_next_element(&iter); 397 } 398 fprintf(stderr, "\n"); 399} 400#endif 401