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