lib/hash.c

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