lib/hash.c

   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