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