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