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