Utilities/cmcurl/lib/hash.c

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