lib/hash.c

   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