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