[352] | 1 | /***************************************************************************
|
---|
| 2 | * _ _ ____ _
|
---|
| 3 | * Project ___| | | | _ \| |
|
---|
| 4 | * / __| | | | |_) | |
|
---|
| 5 | * | (__| |_| | _ <| |___
|
---|
| 6 | * \___|\___/|_| \_\_____|
|
---|
| 7 | *
|
---|
| 8 | * Copyright (C) 1998 - 2017, 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 <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
|
---|